[LLVMdev] LLD improvement plan

[Rui Ueyama]

Hi guys, After working for a long period of time on LLD, I think I found a few things that we should improve in the LLD design for both development ease and runtime performance. I would like to get feedback on this proposal. Thanks! Problems with the current LLD architecture The current LLD architecture has, in my opinion, two issues.

The atom model is not the best model for some architectures The atom model makes sense only for Mach-O, but it’s used everywhere. I guess that we originally expected that we would be able to model the linker’s behavior beautifully using the atom model because the atom model seemed like a superset of the section model. Although it *can*, it turned out that it’s not necessarily natural and efficient model for ELF or PE/COFF on which section-based linking is expected. On ELF or PE/COFF, sections are units of atomic data. We divide a section into smaller “atoms” and then restore the original data layout later to preserve section’s atomicity. That complicates the linker internals. Also it slows down the linker because of the overhead of creating and manipulating atoms. In addition to that, since section-based linking is expected on the architectures, some linker features are defined in terms of sections. An example is “select largest section” in PE/COFF. In the atom model, we don’t have a notion of sections at all, so we had to simulate such features using atoms in tricky ways.

One symbol resolution model doesn’t fit all The symbol resolution semantics are not the same on three architectures (ELF, Mach-O and PE/COFF), but we only have only one "core" linker for the symbol resolution. The core linker implements the Unix linker semantics; the linker visits a file at a time until all undefined symbols are resolved. For archive files having circular dependencies, you can group them to tell the linker to visit them more than once. This is not the only model to create a linker. It’s not the simplest nor fastest. It’s just that the Unix linker semantics is designed this way, and we all follow for compatibility. For PE/COFF, the linker semantics are different. The order of files in the command line doesn’t matter. The linker scans all files first to create a map from symbols to files, and use the map to resolve all undefined symbols. The PE/COFF semantics are currently simulated using the Unix linker semantics and groups. That made the linker inefficient because of the overhead to visit archive files again and again. Also it made the code bloated and awkward. In short, we generalize too much, and we share code too much.

Proposal

1. Re-architect the linker based on the section model where it’s appropriate.
   
2. Stop simulating different linker semantics using the Unix model. Instead, directly implement the native behavior.

When it’s done, the atom model will be used only for Mach-O. The other two will be built based on the section model. PE/COFF will have a different "core" linker than Unix’s. I expect this will simplify the design and also improve the linker’s performance (achieving better performance is probably the best way to convince people to try LLD). I don’t think we can gradually move from the atom model to the section model because atoms are everywhere. They are so different that we cannot mix them together at one place. Although we can reuse the design and the outline the existing code, this is going to be more like a major rewriting rather than updating. So I propose developing section-based ports as new "ports" of LLD. I plan to start working on PE/COFF port first because I’m familiar with the code base and the amount of code is less than the ELF port. Also, the fact that the ELF port is developed and maintained by many developers makes porting harder compared to PE/COFF, which is written and maintained only by me. Thus, I’m going to use PE/COFF as an experiment platform to see how it works. Here is a plan.

1. Create a section-based PE/COFF linker backend as a new port
   
2. If everything is fine, do the same thing for ELF. We may want to move common code for a section-based linker out of the new PE/COFF port to share it with ELF.
3. Move the library for the atom model to the sub-directory for the Mach-O port.

The resulting linker will share less code between ports. That’s not necessarily a bad thing -- we actually think it’s a good thing because in order to share code we currently have too many workarounds. This change should fix the balance so that we get (1) shared code that’s naturally able to be shared by multiple ports, and (2) simpler, faster code.

Work Estimation It’s hard to tell, but I’m probably able to create a PE/COFF linker in a few weeks, which works reasonably well and ready for code review as a first set of patches. I have already built a complete linker for Windows, so the hardest part (understanding it) is already done.

Once it’s done, I can get a better estimation for ELF.

Caveat Why not define a section as an atom and keep using the atom model? If we do this, we would have to allow atoms to have more than one name. Each name would have an offset in the atom (to represent symbols whose offset from the section start is not zero). But still we need to copy section attributes to each atom. The resulting model no longer looks like the atom model, but a mix of the atom model and the section model, and that comes with the cost of both designs. I think it’s too complicated.

Notes

We want to make sure there’s no existing LLD users who depend on the atom model for ELF, or if there’s such users, we want to come up with a transition path for them.

[Michael Spencer]

On Fri, May 1, 2015 at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:
> Caveat Why not define a section as an atom and keep using the atom model? If
> we do this, we would have to allow atoms to have more than one name. Each
> name would have an offset in the atom (to represent symbols whose offset
> from the section start is not zero). But still we need to copy section
> attributes to each atom. The resulting model no longer looks like the atom
> model, but a mix of the atom model and the section model, and that comes
> with the cost of both designs. I think it’s too complicated.

Rafael and I have been discussing this change recently. It makes atoms
actually atomic, and also splits out symbols, which has been needed.
The main reason I like this over each target having its own model is
because it gives us a common textual representation to write tests
with.

As for symbol resolution. It seems the actual problem is name lookup,
not the core resolver semantics.

I'd rather not end up with basically 3 separate linkers in lld.

- Michael Spencer

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Rui Ueyama]

On Fri, May 1, 2015 at 1:32 PM, Michael Spencer <bigch...@gmail.com> wrote:

On Fri, May 1, 2015 at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:
> Caveat Why not define a section as an atom and keep using the atom model? If
> we do this, we would have to allow atoms to have more than one name. Each
> name would have an offset in the atom (to represent symbols whose offset
> from the section start is not zero). But still we need to copy section
> attributes to each atom. The resulting model no longer looks like the atom
> model, but a mix of the atom model and the section model, and that comes
> with the cost of both designs. I think it’s too complicated.

Rafael and I have been discussing this change recently. It makes atoms
actually atomic, and also splits out symbols, which has been needed.
The main reason I like this over each target having its own model is
because it gives us a common textual representation to write tests
with.

If you allow multiple symbols in one atom, is the new definition of atom different from section? If so, in what way?

As for symbol resolution. It seems the actual problem is name lookup,
not the core resolver semantics.

What's the difference between name lookup and the core resolver semantics?

 

I'd rather not end up with basically 3 separate linkers in lld.

I basically agree. However, if you take a look at the code of the PE/COFF port, you'll find something weird here and there.

[Michael Spencer]

On Fri, May 1, 2015 at 1:42 PM, Rui Ueyama <ru...@google.com> wrote:
> On Fri, May 1, 2015 at 1:32 PM, Michael Spencer <bigch...@gmail.com>
> wrote:
>>
>> On Fri, May 1, 2015 at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:
>> > Caveat Why not define a section as an atom and keep using the atom
>> > model? If
>> > we do this, we would have to allow atoms to have more than one name.
>> > Each
>> > name would have an offset in the atom (to represent symbols whose offset
>> > from the section start is not zero). But still we need to copy section
>> > attributes to each atom. The resulting model no longer looks like the
>> > atom
>> > model, but a mix of the atom model and the section model, and that comes
>> > with the cost of both designs. I think it’s too complicated.
>>
>> Rafael and I have been discussing this change recently. It makes atoms
>> actually atomic, and also splits out symbols, which has been needed.
>> The main reason I like this over each target having its own model is
>> because it gives us a common textual representation to write tests
>> with.
>
>
> If you allow multiple symbols in one atom, is the new definition of atom
> different from section? If so, in what way?

It's pretty much the same. I read what you said as having a different
section representation for each target.

>
>> As for symbol resolution. It seems the actual problem is name lookup,
>> not the core resolver semantics.
>
>
> What's the difference between name lookup and the core resolver semantics?
>

Name lookup would be how it finds what symbols to consider for
resolving. The core resolver semantics is mostly
SymbolTable::addByName.

- Michael Spencer

>>
>> I'd rather not end up with basically 3 separate linkers in lld.
>
>
> I basically agree. However, if you take a look at the code of the PE/COFF
> port, you'll find something weird here and there.

_______________________________________________

[Rui Ueyama]

On Fri, May 1, 2015 at 2:10 PM, Michael Spencer <bigch...@gmail.com> wrote:

On Fri, May 1, 2015 at 1:42 PM, Rui Ueyama <ru...@google.com> wrote:
> On Fri, May 1, 2015 at 1:32 PM, Michael Spencer <bigch...@gmail.com>
> wrote:
>>
>> On Fri, May 1, 2015 at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:
>> > Caveat Why not define a section as an atom and keep using the atom
>> > model? If
>> > we do this, we would have to allow atoms to have more than one name.
>> > Each
>> > name would have an offset in the atom (to represent symbols whose offset
>> > from the section start is not zero). But still we need to copy section
>> > attributes to each atom. The resulting model no longer looks like the
>> > atom
>> > model, but a mix of the atom model and the section model, and that comes
>> > with the cost of both designs. I think it’s too complicated.
>>
>> Rafael and I have been discussing this change recently. It makes atoms
>> actually atomic, and also splits out symbols, which has been needed.
>> The main reason I like this over each target having its own model is
>> because it gives us a common textual representation to write tests
>> with.
>
>
> If you allow multiple symbols in one atom, is the new definition of atom
> different from section? If so, in what way?

It's pretty much the same. I read what you said as having a different
section representation for each target.

No, the class definition for the section for PE/COFF and ELF would be the same. Also if we can use that for Mach-O, we should use that too. And if it's the same as section, I'd call it section rather than atom.

 

>
>> As for symbol resolution. It seems the actual problem is name lookup,
>> not the core resolver semantics.
>
>
> What's the difference between name lookup and the core resolver semantics?
>

Name lookup would be how it finds what symbols to consider for
resolving. The core resolver semantics is mostly
SymbolTable::addByName.

Yeah, how we resolve (conflicting) symbols is mostly the same, and the difference is in how we find files defining undefined symbols.

[Rafael Espíndola]

I am on the airport waiting to go on vacations, but I must say I am extremely happy to see this happen!

I agree with the proposed direction and steps:

Implement section based linking for coff.

Use that for elf.

If it makes sense, use it for macho.

[Nick Kledzik]

On May 1, 2015, at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:

The atom model is not the best model for some architectures

The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom.  

The problem is the ELF/PECOFF file format.   (Actually mach-o is also section based, but we have refrained from adding complex section-centric features to it, so mapping it to atoms is not too hard).

I’d rather see our effort put to moving ahead to an llvm based object file format (aka “native” format) which bypasses the impedance mismatch of going through ELF/COFF.  

One symbol resolution model doesn’t fit all

Yes, the Resolver was meant to call out to the LinkingContext object to direct it on how to link.  Somehow that got morphed into “there should be a universal data model that when the Resolver process the input data, the right platform specific linking behavior falls out”.  

-Nick

[Rafael Espíndola]

On May 1, 2015 9:42 PM, "Nick Kledzik" <kle...@apple.com> wrote:
>
>
> On May 1, 2015, at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:
>>
>> The atom model is not the best model for some architectures
>
>
> The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom.  

That is not the input to the linker and therefore irrelevant.

> The problem is the ELF/PECOFF file format.   (Actually mach-o is also section based, but we have refrained from adding complex section-centric features to it, so mapping it to atoms is not too hard).

The objective is to build an elf and coff linker. The input has sections and splitting them is a total waste of time and extra design complexity.

> I’d rather see our effort put to moving ahead to an llvm based object file format (aka “native” format) which bypasses the impedance mismatch of going through ELF/COFF.  

Absolutely not. We have to be able to handle elf and coff and do it well.

Also, gold shows that elf at least works extremely well. With function sections the compiler is in complete control of the size of the units the linker uses. With my recent work on MC the representation is also very efficient. I have no reason to believe coff is any different.

Cheers,
Rafael

[Chandler Carruth]

On Fri, May 1, 2015 at 6:46 PM Nick Kledzik <kle...@apple.com> wrote:

On May 1, 2015, at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:

The atom model is not the best model for some architectures

The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom.

I'm not sure how that's really relevant.

On some architectures, the unit at which linking is defined to occur isn't a global object. A classic example of this are architectures that have a hard semantic reliance grouping two symbols together and linking either both or neither of them.

 

The problem is the ELF/PECOFF file format.   (Actually mach-o is also section based, but we have refrained from adding complex section-centric features to it, so mapping it to atoms is not too hard).

I’d rather see our effort put to moving ahead to an llvm based object file format (aka “native” format) which bypasses the impedance mismatch of going through ELF/COFF.

We still have to be able to (efficiently) link existing ELF and COFF objects though? While I'm actually pretty interested in some better object file format, I also want a better linker for the world we live in today...

 

 

One symbol resolution model doesn’t fit all

Yes, the Resolver was meant to call out to the LinkingContext object to direct it on how to link.  Somehow that got morphed into “there should be a universal data model that when the Resolver process the input data, the right platform specific linking behavior falls out”.  

-Nick

[Alex Rosenberg]

On May 1, 2015, at 7:06 PM, Chandler Carruth <chan...@google.com> wrote:

On Fri, May 1, 2015 at 6:46 PM Nick Kledzik <kle...@apple.com> wrote:

On May 1, 2015, at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:

The atom model is not the best model for some architectures

The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom.

I'm not sure how that's really relevant.

On some architectures, the unit at which linking is defined to occur isn't a global object. A classic example of this are architectures that have a hard semantic reliance grouping two symbols together and linking either both or neither of them.

 

The problem is the ELF/PECOFF file format.   (Actually mach-o is also section based, but we have refrained from adding complex section-centric features to it, so mapping it to atoms is not too hard).

I’d rather see our effort put to moving ahead to an llvm based object file format (aka “native” format) which bypasses the impedance mismatch of going through ELF/COFF.

We still have to be able to (efficiently) link existing ELF and COFF objects though? While I'm actually pretty interested in some better object file format, I also want a better linker for the world we live in today...

For us, this is secondary. A major part of the reason we started lld was to embrace the atom model, that is to bring the linker closer to the compiler. We have a lot of long-term goals that involve altering the traditional compiler/linker flow, with a goal toward actual improvements in developer workflow. Just iterating again on the exact same design we've had since the '70s is not good enough.

The same is true of other legacy we're inheriting like linker scripts. While we want them to work and work efficiently, we should consider them part of necessary legacy to support and not make them fundamental to our internal design. This planning will allow us latitude to make fundamental improvements. We make similar decisions across LLVM all the time, take our attitude toward __builtin_constant_p() or nested functions for example.

We've been at this for several years. We had goals and deadlines that we're not meeting. We've abandoned several significant design points so far because Rui is making progress on PECOFF and jettisons things and we let it slide because of his rapid pace.

Core command line? GONE.

Round-trip testing? GONE.

Native file format? GONE.

And now we're against the Atom model?

I don't want a new linker that just happens to be so mired in the same legacy that we've ended up with nothing but a gratuitous rewrite with a better license.

We want:

* A new clean command line that obviates the need for linker scripts and their incestuous design requirements.

* lld is thoroughly tested, including the efficient new native object file format it provides.

* lld is like the rest of LLVM and can be remixed such that it's built-in to the Clang driver, should we choose to.

* We can have the linker drive compilation such that objects don't leave the disk cache before being consumed by the linker.

Perhaps we should schedule an in-person lld meeting. Almost everybody is in the Bay Area. I'm happy to host if we think this will help.

Alex

[Rui Ueyama]

It is not a secondary goal for me to create a linker that works very well with existing file formats. I'm trying to create a practical tool with clean codebase and with the LLVM library. So I can't agree with you that it's secondary.

I don't also share the view that we are trying to solve the problem that's solved in '70s. How fast we can link a several hundred megabyte executable is, for example, a pretty modern problem that we have today.

I don't oppose to the idea of creating a new file format that you think better than the existing ones. We may come up with a better design, implement that to the compiler, set out the foundation, and create a linker based on that. However, what's actually happening is coming up with a new idea which is not necessarily best to represent existing file formats, set out the foundation based on that idea, and let LLD developers create a linker for the existing formats base on the foundation (which is, again, is not suitable for the formats). And there was no efforts made in the recent few years for "the new format". I have to say that something is not correct here.

[Davide Italiano]

> _______________________________________________
> LLVM Developers mailing list
> LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

There are projects (like FreeBSD) which need a new linker.
In the FreeBSD case it is mainly motivated by a licensing issue, but I
feel like this doesn't mean that the linker needs to be slower or
harder to hack on because we want to treat as first class citizen a
format that has been largely unmaintained in the last 6 months at
least and as second class citizen widespread formats like ELF. I'm
personally excited about the idea of a new format and I would like to
spend some time thinking about it, although I always try to be
pragmatic.
I will be happy to discuss this further in person.

--
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare

[James Courtier-Dutton]

On 1 May 2015 at 20:31, Rui Ueyama <ru...@google.com> wrote:
>
> One symbol resolution model doesn’t fit all The symbol resolution semantics
> are not the same on three architectures (ELF, Mach-O and PE/COFF), but we
> only have only one "core" linker for the symbol resolution. The core linker
> implements the Unix linker semantics; the linker visits a file at a time
> until all undefined symbols are resolved. For archive files having circular
> dependencies, you can group them to tell the linker to visit them more than
> once. This is not the only model to create a linker. It’s not the simplest
> nor fastest. It’s just that the Unix linker semantics is designed this way,
> and we all follow for compatibility. For PE/COFF, the linker semantics are
> different. The order of files in the command line doesn’t matter. The linker
> scans all files first to create a map from symbols to files, and use the map
> to resolve all undefined symbols. The PE/COFF semantics are currently
> simulated using the Unix linker semantics and groups. That made the linker
> inefficient because of the overhead to visit archive files again and again.
> Also it made the code bloated and awkward. In short, we generalize too much,
> and we share code too much.
>

Why can't LLD be free to implement a resolving algorithm that performs better.
The PE/COFF method you describe seems more efficient that the existing
ELF method.
What is stopping LLD from using the PE/COFF method for ELF. It could
also do further optimizations such as caching the resolved symbols.
To me,the existing algorithms read as ELF == Full table scan, PE/COEF
== Indexed.

Also, could some of the symbol resolution be done at compile time?
E.g. If I include stdio.h, I know which link time library that is
associated with, so I can resolve those symbols at compile time.
Maybe we could store that information in the pre-compiled headers file
format, and subsequently in the .o files.
This would then leave far fewer symbols to resolve at link time.

Kind Regards

James

[Joerg Sonnenberger]

On Mon, May 04, 2015 at 09:29:16AM +0100, James Courtier-Dutton wrote:
> Also, could some of the symbol resolution be done at compile time?
> E.g. If I include stdio.h, I know which link time library that is
> associated with, so I can resolve those symbols at compile time.

Where would you get that information from? No such tagging exists in
standard C or even the extended dialect of C clang is implementing.

Joerg

[James Y Knight]

And now we're against the Atom model?

I'm quite new to the llvm community, and basically unfamiliar with LLD, so maybe I'm simply uninformed. If so, I will now proceed to demonstrate that to an entire list of people. :)

I've read the doc on http://lld.llvm.org/design.html, but the list of features it says that you get with LLD/Atoms and don't get with the "old generation" of linkers that use "sections"...are all things that ELF linkers already do using sections, and do not require anything finer grained than sections. Sections in ELF objects can actually be as fine-grained as you want them to be -- just as an "Atom". Doc also says, "An atom is an indivisible chunk of code or data." -- which is also what a section is for ELF.

AFAICT, atoms in LLD are simply a restricted form of ELF sections: restricted to having a single symbol associated with them. It doesn't appear that they're actually enabling any new features that no other linker can do.

I'm not very familiar with Mach-O, but it sounds like, contrary to ELF, Mach-O files cannot be generated with one section per global object, but that Mach-O sections (at least as used by OSX) *are* expected to be subdivided/rearranged/etc, and are not atomic. Given that set of properties for the input file format, of course it makes sense that you'd want to subdivide Mach-O "sections" within the linker into smaller atomic pieces to work on them.

But for ELF, the compiler can/will output separate sections for each function/global variable, and the contents of a section should never be mangled. It can also emit multiple symbols into a single section. That an ELF section *may* contain multiple functions/globals which need to stay together is not a problem with the file format -- it's an advantage -- an additional flexibility of representation.

I gather the current model in LLD doesn't support an atomic unit with multiple symbols cleanly. And that that's the main issue that would be good to fix here.

But, rather than talking about "eliminating the atom model" -- which seems to be contentious -- maybe it would be more peaceful to just say that the desired change is to "allow atoms to have multiple global symbols associated, and have more metadata"? It appears to me that it amounts to essentially the same thing, but may not be as contentious if described that way.

If that change was made, you'd just need to know that LLD has slightly unique terminology; "ELF section" == "LLD Atom". (but "Mach-O section" turns into multiple "LLD Atom"s).

Am I wrong?

James

[Reid Kleckner]

Most of what I wanted to say has been said, but I wanted to explicitly call out COMDAT groups as something that we want that doesn't fit the atom model very well.

Adding first class COMDATs was necessary for implementing large parts of the Microsoft C++ ABI, but it also turns out that it's really handy on other platforms. We've made a number of changes to Clang's IRgen to do things like eliminate duplicate dynamic initialization for static data members of class templates and share code for complete, base, and deleting destructors.

Basically, COMDAT groups are a tool that the compiler can use to change the way things are linked without changing the linker. They allow the compiler to add new functionality and reduce coupling between the compiler and the linker. This is a real tradeoff worth thinking about.

I think for many platforms (Windows, Linux) Clang is not the system compiler and we need to support efficiently linking against existing libraries for a long time to come. There are other platforms (Mac, PS4) with a single toolchain where controlling the linker allows adding new functionality quickly.

I think Alex is right, we should probably meet some time and figure out what people need and how to support both kinds of platform well.

Reid

[Rui Ueyama]

The two semantics are not compatible. The results of the two are not always the same.

For example, this is why we have to pass -lc after object files instead of the beginning of the command line. "ln -lc foo.o" would just skip libc because when it visits the library, there's no undefined symbols to be resolved. foo.o would then add undefined symbols that could have been resolved using libc, but it's too late. The link would fail. This is how linkers on Unix works. There are other differences resulting from the difference, so we cannot change that unless we break the compatibility.

Also, could some of the symbol resolution be done at compile time?
E.g. If I include stdio.h, I know which link time library that is
associated with, so I can resolve those symbols at compile time.
Maybe we could store that information in the pre-compiled headers file
format, and subsequently in the .o files.
This would then leave far fewer symbols to resolve at link time.

You can link against an alternative libc, for example, so that's not usually doable.

[Sean Silva]

On Sun, May 3, 2015 at 3:13 PM, Rui Ueyama <ru...@google.com> wrote:

It is not a secondary goal for me to create a linker that works very well with existing file formats. I'm trying to create a practical tool with clean codebase and with the LLVM library. So I can't agree with you that it's secondary.

I don't also share the view that we are trying to solve the problem that's solved in '70s. How fast we can link a several hundred megabyte executable is, for example, a pretty modern problem that we have today.

I don't think Alex was trying to say that we're solving the same problem. I think he his trying to say that we are trying to solve our current problems with the same tool flow as was used in the 70's.

-- Sean Silva

 

[Chris Lattner]

On May 1, 2015, at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:

Proposal

1. Re-architect the linker based on the section model where it’s appropriate.
   
2. Stop simulating different linker semantics using the Unix model. Instead, directly implement the native behavior.

Preface: I have never personally contributed code to LLD, so don’t take anything I’m about to say too seriously.  This is not a mandate or anything, just an observation/idea.

I think that there is an alternative solution to these exact same problems.  What you’ve identified here is that there are two camps of people working on LLD, and they have conflicting goals:

- Camp A: LLD is infrastructure for the next generation of awesome linking and toolchain features, it should take advantage of how compilers work to offer new features, performance, etc without deep concern for compatibility.

- Camp B: LLD is a drop in replacement system linker (notably for COFF and ELF systems), which is best of breed and with no compromises w.r.t. that goal.

I think the problem here is that these lead to natural and inescapable tensions, and Alex summarized how Camp B has been steering LLD away from what Camp A people want.  This isn’t bad in and of itself, because what Camp B wants is clearly and unarguably good for LLVM.  However, it is also not sufficient, and while innovation in the linker space (e.g. a new “native” object file format generated directly from compiler structures) may or may not actually “work” or be “worth it”, we won’t know unless we try, and that won’t fulfill its promise if there are compromises to Camp B.

So here’s my counterproposal: two different linkers.

Lets stop thinking about lld as one linker, and instead think of it is two different ones.  We’ll build a Camp B linker which is the best of breed section based linker.  It will support linker scripts and do everything better than any existing section based linker.  The first step of this is to do what Rui proposes and rip atoms out of the model.

We will also build a no-holds-barred awesome atom based linker that takes advantage of everything it can from LLVM’s architecture to enable innovative new tools without worrying too much about backwards compatibility.

These two linkers should share whatever code makes sense, but also shouldn’t try to share code that doesn’t make sense.  The split between the semantic model of sections vs atoms seems like a very natural one to me.

One question is: does it make sense for these to live in the same lld subproject, or be split into two different subprojects?  I think the answer to that question is driven from whether there is shared code common between the two linkers that doesn’t make sense to sink down to the llvm subproject itself.

What do you think?

-Chris

[Joerg Sonnenberger]

On Mon, May 04, 2015 at 12:52:55PM -0700, Chris Lattner wrote:
> I think the problem here is that these lead to natural and inescapable
> tensions, and Alex summarized how Camp B has been steering LLD away
> from what Camp A people want. This isn’t bad in and of itself, because
> what Camp B wants is clearly and unarguably good for LLVM. However,
> it is also not sufficient, and while innovation in the linker space
> (e.g. a new “native” object file format generated directly from
> compiler structures) may or may not actually “work” or be “worth it”,
> we won’t know unless we try, and that won’t fulfill its promise if
> there are compromises to Camp B.

It has been said in this thread before, but I fail to see how the atom
model is an actual improvement over the fine grained section model. It
seems to be artifically restricted for no good reasons.

> Lets stop thinking about lld as one linker, and instead think of it is
> two different ones. We’ll build a Camp B linker which is the best of
> breed section based linker. It will support linker scripts and do
> everything better than any existing section based linker. The first
> step of this is to do what Rui proposes and rip atoms out of the model.

This is another item that has been irritating me. While it is a very
laudable goal to not depend on linker scripts for the common case, not
having the functionality of fine grained output control is certainly a
problem. They are crucial for embedded developers and also at least
significant for anything near a system kernel.

> We will also build a no-holds-barred awesome atom based linker that
> takes advantage of everything it can from LLVM’s architecture to enable
> innovative new tools without worrying too much about backwards
> compatibility.

I'd say that a good justificatiton for way an atom based linker is/can
be better would be a good start...

Joerg

[Chris Lattner]

On May 4, 2015, at 1:16 PM, Joerg Sonnenberger <jo...@britannica.bec.de> wrote:
> It has been said in this thread before, but I fail to see how the atom
> model is an actual improvement over the fine grained section model. It
> seems to be artifically restricted for no good reasons.

Sections come with a huge amount of bloat and overhead that atoms do not.

>> Lets stop thinking about lld as one linker, and instead think of it is
>> two different ones. We’ll build a Camp B linker which is the best of
>> breed section based linker. It will support linker scripts and do
>> everything better than any existing section based linker. The first
>> step of this is to do what Rui proposes and rip atoms out of the model.
>
> This is another item that has been irritating me. While it is a very
> laudable goal to not depend on linker scripts for the common case, not
> having the functionality of fine grained output control is certainly a
> problem. They are crucial for embedded developers and also at least
> significant for anything near a system kernel.

I’m not saying that the linker should eschew fine grained control, I’m saying it should dump linker scripts (and replace them with something better). Are you going to argue that linker scripts are great, or that they are what we would end up with if we weren’t driven by backwards compatibility goals?

-Chris

[Eric Christopher]

On Mon, May 4, 2015 at 3:08 PM Chris Lattner <clat...@apple.com> wrote:

On May 4, 2015, at 1:16 PM, Joerg Sonnenberger <jo...@britannica.bec.de> wrote:
> It has been said in this thread before, but I fail to see how the atom
> model is an actual improvement over the fine grained section model. It
> seems to be artifically restricted for no good reasons.

Sections come with a huge amount of bloat and overhead that atoms do not.

Caveat: My response isn't in favor of one way over the other, but providing some explanations or trying to frame the trade-offs in a more explicit form.

Sections come with _some_ size overhead that an atom doesn't because an atom is contained within a section, however, atoms come with a link time cost that sections don't. Trade off. :)

The atom model is effective for minimizing the size of on disk representation or working around limited object container formats. Being able to just append sections is a trade off for speed of linking versus size of inputs at the moment (which is a tricky trade-off as the speed of linking starts to approach the size of the objects being linked). That said, I don't think any of the current linkers are currently I/O bound here either.

 

>> Lets stop thinking about lld as one linker, and instead think of it is
>> two different ones.  We’ll build a Camp B linker which is the best of
>> breed section based linker.  It will support linker scripts and do
>> everything better than any existing section based linker.  The first
>> step of this is to do what Rui proposes and rip atoms out of the model.
>
> This is another item that has been irritating me. While it is a very
> laudable goal to not depend on linker scripts for the common case, not
> having the functionality of fine grained output control is certainly a
> problem. They are crucial for embedded developers and also at least
> significant for anything near a system kernel.

I’m not saying that the linker should eschew fine grained control, I’m saying it should dump linker scripts (and replace them with something better).  Are you going to argue that linker scripts are great, or that they are what we would end up with if we weren’t driven by backwards compatibility goals?

Linker scripts are worse than everything - except for the alternatives that we know about. Any particular suggestions here?

-eric 

[Joerg Sonnenberger]

On Mon, May 04, 2015 at 03:05:47PM -0700, Chris Lattner wrote:
> On May 4, 2015, at 1:16 PM, Joerg Sonnenberger <jo...@britannica.bec.de> wrote:
> > It has been said in this thread before, but I fail to see how the atom
> > model is an actual improvement over the fine grained section model. It
> > seems to be artifically restricted for no good reasons.
>
> Sections come with a huge amount of bloat and overhead that atoms do not.

I don't buy that as far as the internal representation is concerned.
On-disk format as Eric said is a somewhat different question.

> >> Lets stop thinking about lld as one linker, and instead think of it is
> >> two different ones. We’ll build a Camp B linker which is the best of
> >> breed section based linker. It will support linker scripts and do
> >> everything better than any existing section based linker. The first
> >> step of this is to do what Rui proposes and rip atoms out of the model.
> >
> > This is another item that has been irritating me. While it is a very
> > laudable goal to not depend on linker scripts for the common case, not
> > having the functionality of fine grained output control is certainly a
> > problem. They are crucial for embedded developers and also at least
> > significant for anything near a system kernel.
>
> I’m not saying that the linker should eschew fine grained control, I’m
> saying it should dump linker scripts (and replace them with something
> better). Are you going to argue that linker scripts are great, or that
> they are what we would end up with if we weren’t driven by backwards
> compatibility goals?

I haven't seen the better alternative yet. It is hard to reason about
vaporware. I'm not particulary attached to linker scripts, they are
certainly a horrible language. But the lack of support is certainly a
show stopper for those areas where the functionality is needed.
How is a linker supporting at least a major part of that functionality
going to be different from a linker that accepts linker scripts as
input?

Joerg

[Meador Inge]

On Mon, May 04, 2015 at 10:15:51PM +0000, Eric Christopher wrote:

> Linker scripts are worse than everything - except for the alternatives that
> we know about. Any particular suggestions here?

I very much care about the functionality provided by linker scripts (for
embedded systems and kernel work), but I do agree that most current
script formats are hard to use, debug, reason about, etc... I have
often wondered whether embedding Python might be a better choice.

Take a look at how debuggers have migrated through the years. They too
used to have their own script format. Now most (all?) popular debuggers
do scripting through embedding an actual programming language. This
could be a better way forward for linkers as well -- embed Python in the
linker, define a Python API for linkable item placement, entry point,
symbol operations, etc..., and then you also have the rest of Python at
your fingertips.

-- Meador

[Daniel Dilts]

> Linker scripts are worse than everything - except for the alternatives that
> we know about. Any particular suggestions here?

I very much care about the functionality provided by linker scripts (for
embedded systems and kernel work), but I do agree that most current
script formats are hard to use, debug, reason about, etc...  I have
often wondered whether embedding Python might be a better choice.

Take a look at how debuggers have migrated through the years.  They too
used to have their own script format.  Now most (all?) popular debuggers
do scripting through embedding an actual programming language.  This
could be a better way forward for linkers as well -- embed Python in the
linker, define a Python API for linkable item placement, entry point,
symbol operations, etc..., and then you also have the rest of Python at
your fingertips.

I mostly care about specifying address where specific symbols will be placed and specifying the memory layout of the platform.   I normally use __attribute__((section(""))) to place the symbols in their own sections and then use the linker script to place the sections at the required addresses.  How would this be accomplished without linker scripts?

[Chris Lattner]

On May 5, 2015, at 6:47 PM, Daniel Dilts <dilt...@gmail.com> wrote:

Take a look at how debuggers have migrated through the years.  They too

used to have their own script format.  Now most (all?) popular debuggers
do scripting through embedding an actual programming language.  This
could be a better way forward for linkers as well -- embed Python in the
linker, define a Python API for linkable item placement, entry point,
symbol operations, etc..., and then you also have the rest of Python at
your fingertips.

I mostly care about specifying address where specific symbols will be placed and specifying the memory layout of the platform.   I normally use __attribute__((section(""))) to place the symbols in their own sections and then use the linker script to place the sections at the required addresses.  How would this be accomplished without linker scripts?

I’d prefer to use an "__attribute__((address(0x1234)))” myself.  That way you can control platform specifics with #ifdefs.

-Chris

[Will Newton]

But that way you have to do layout by hand in C. Generally you won't
know the size of the preceding code or data so you won't know what
address to put things at at the granularity of a single C level
object/function. Better to say "put this in the ROM section" and set
the address of the ROM section once in a linker script and let the
linker do the layout.

[Daniel Dilts]

On Wed, May 6, 2015 at 12:51 AM, Will Newton <will....@gmail.com> wrote:

On Wed, May 6, 2015 at 6:22 AM, Chris Lattner <clat...@apple.com> wrote:
> On May 5, 2015, at 6:47 PM, Daniel Dilts <dilt...@gmail.com> wrote:
>
> Take a look at how debuggers have migrated through the years.  They too
>>
>> used to have their own script format.  Now most (all?) popular debuggers
>> do scripting through embedding an actual programming language.  This
>> could be a better way forward for linkers as well -- embed Python in the
>> linker, define a Python API for linkable item placement, entry point,
>> symbol operations, etc..., and then you also have the rest of Python at
>> your fingertips.
>
>
> I mostly care about specifying address where specific symbols will be placed
> and specifying the memory layout of the platform.   I normally use
> __attribute__((section(""))) to place the symbols in their own sections and
> then use the linker script to place the sections at the required addresses.
> How would this be accomplished without linker scripts?
>
>
> I’d prefer to use an "__attribute__((address(0x1234)))” myself.  That way
> you can control platform specifics with #ifdefs.

But that way you have to do layout by hand in C. Generally you won't
know the size of the preceding code or data so you won't know what
address to put things at at the granularity of a single C level
object/function. Better to say "put this in the ROM section" and set
the address of the ROM section once in a linker script and let the
linker do the layout.

The real use case is on platforms, like ARM, where control registers are mapped to a specific address range.  Then it is useful to put an object that deals with the control registers at a specific address.  __attribute__((address(0x1234))) can be replaced with a platform specific linker script.  Which is better?  I don't know, I haven't spent any time comparing them. 

[Will Newton]

Why would you want to put an object at the address of some registers?
You would just want a cast would you not?

e.g. regs = (struct MyRegBlock *)0x1234

[Sean Silva]

There is another important use of linker scripts, namely having a notion of separate load and virtual addresses. This is important for e.g. an initialized .data section which is stored in ROM, but needs to be copied to writable memory.

For more information on linker scripts, see my post "linker script findings": http://marc.info/?l=llvm-dev&m=135698146015498&w=2

-- Sean Silva

[Sean Silva]

On Wed, May 6, 2015 at 12:51 AM, Will Newton <will....@gmail.com> wrote:

On Wed, May 6, 2015 at 6:22 AM, Chris Lattner <clat...@apple.com> wrote:
> On May 5, 2015, at 6:47 PM, Daniel Dilts <dilt...@gmail.com> wrote:
>
> Take a look at how debuggers have migrated through the years.  They too
>>
>> used to have their own script format.  Now most (all?) popular debuggers
>> do scripting through embedding an actual programming language.  This
>> could be a better way forward for linkers as well -- embed Python in the
>> linker, define a Python API for linkable item placement, entry point,
>> symbol operations, etc..., and then you also have the rest of Python at
>> your fingertips.
>
>
> I mostly care about specifying address where specific symbols will be placed
> and specifying the memory layout of the platform.   I normally use
> __attribute__((section(""))) to place the symbols in their own sections and
> then use the linker script to place the sections at the required addresses.
> How would this be accomplished without linker scripts?
>
>
> I’d prefer to use an "__attribute__((address(0x1234)))” myself.  That way
> you can control platform specifics with #ifdefs.

But that way you have to do layout by hand in C. Generally you won't
know the size of the preceding code or data so you won't know what
address to put things at at the granularity of a single C level
object/function. Better to say "put this in the ROM section" and set
the address of the ROM section once in a linker script and let the
linker do the layout.

Chris is referring to memory-mapped registers that are literally at a fixed address in the hardware. These sorts of attributes already exist, e.g. https://gcc.gnu.org/onlinedocs/gcc/AVR-Variable-Attributes.html#AVR-Variable-Attributes

[Sean Silva]

This causes you to have to be constantly dereferencing, which can result in a huge amount of syntactic overhead. CMSIS does this really consistently and do a good job at it: http://www.keil.com/pack/doc/CMSIS/Core/html/group__peripheral__gr.html

But it's sort of an all-or-nothing thing to organize the peripheral headers like that, and many platforms don't (MSP430, AVR, smaller PIC's), instead preferring to have e.g. `volatile uint8_t Foo;` for each hardware register instead of putting things in structs.

-- Sean Silva

[Rick Mann]

Having worked with both forms (struct vs. individual symbols), I really prefer the struct mechanism. Especially in more recent processors, the hardware register layout is very consistent from one peripheral to the next, and when using the struct, it can dramatically reduce the number of symbols one has to deal with.

So, my $0.02 (having only a cursory understanding of this thread) is to hopefully allow the struct mechanism.

--
Rick Mann
rm...@latencyzero.com

[Smith, Kevin B]

While slightly off topic of LLD improvement,

 

volatile uint8_t __attribute__((address(0x1234))) foo;

 

is slightly nicer than

 

(*(volatile uint8_t *)0x1234)

 

because the latter ends up often being done in a header file as a macro, usually as something like:

 

#define foo (*(volatile uint8_t *)0x1234)

 

The former behaves with all the language scoping rules, so a foo within a function or as a parameter has the expected

behavior.  The latter has all the downsides that macro usage can come with.

 

On topic – Sean – I think that is a great document on linker scripts and their usage and meaning.

 

Kevin Smith

[Rui Ueyama]

I'm sorry if my suggestion gave an impression that I disregard the Mach-O port of the LLD linker. I do care about Mach-O. I do not plan to break or remove any functionality from the current Mach-O port of the LLD. I don't propose to remove the atom model from the linker as long as it seems to be a good fit for the port (and looks like it is).

As to the proposal to have two different linkers, I'd think that that's not really a counter-proposal, as it's similar to what I'm proposing.

Maybe the view of "future file formats vs the existing formats" (or "experimental platform vs. practical tool") is not right to get the difference between the atom model and the section model, since the Mach-O file an existing file format which we'd want to keep to be on the atom model. I think we want both even for the existing formats.

My proposal can be read as suggesting we split the LLD linker into two major parts, the atom model-based and the section model-based, while keeping the two under the same project and repository. I still think that we can share code between the two, especially for the LTO, which is I prefer to have the two under the same repository.

[Chris Lattner]

> On May 6, 2015, at 2:18 PM, Rui Ueyama <ru...@google.com> wrote:
>
> I'm sorry if my suggestion gave an impression that I disregard the Mach-O port of the LLD linker. I do care about Mach-O. I do not plan to break or remove any functionality from the current Mach-O port of the LLD. I don't propose to remove the atom model from the linker as long as it seems to be a good fit for the port (and looks like it is).
>
> As to the proposal to have two different linkers, I'd think that that's not really a counter-proposal, as it's similar to what I'm proposing.
>
> Maybe the view of "future file formats vs the existing formats" (or "experimental platform vs. practical tool") is not right to get the difference between the atom model and the section model, since the Mach-O file an existing file format which we'd want to keep to be on the atom model. I think we want both even for the existing formats.
>
> My proposal can be read as suggesting we split the LLD linker into two major parts, the atom model-based and the section model-based, while keeping the two under the same project and repository. I still think that we can share code between the two, especially for the LTO, which is I prefer to have the two under the same repository.

That approach makes sense to me personally.

-Chris

[Richard Pennington]

On 05/06/2015 03:06 PM, Sean Silva wrote:

[snip]

The real use case is on platforms, like ARM, where control registers are mapped to a specific address range.  Then it is useful to put an object that deals with the control registers at a specific address.  __attribute__((address(0x1234))) can be replaced with a platform specific linker script.  Which is better?  I don't know, I haven't spent any time comparing them. 

There is another important use of linker scripts, namely having a notion of separate load and virtual addresses. This is important for e.g. an initialized .data section which is stored in ROM, but needs to be copied to writable memory.

For more information on linker scripts, see my post "linker script findings": http://marc.info/?l=llvm-dev&m=135698146015498&w=2

[snip]

Nice write up Sean.
I'd like to second the notion that linker scripts are important, especially in the embedded/kernel world. I use linker scripts to give addresses to register blocks and to put R/W initialized data in flash that can be copied to RAM on start up.
One cool thing about putting register addresses in linker scripts is that you can change the placement of registers without having to rebuild the source. For example, I have a small embedded kernel that can run in both MMU and non-MMU mode. In the former case the peripheral registers are mapped into the kernel's virtual address space, in the latter case they are placed at their actual address. It is nice to be able to do that without having to recompile drivers.

Having said that, I would be all for a new linker script format. I find the GNU linker's scripts counter intuitive and hard to read. The lack of linker scripts is the main thing that keeps me from being able to use lld right now.

-Rich

[Shankar Easwaran]

Hi,

There are a lot of advantages to keep on improving the atom model and working on that model.

The atom model allowed lld to have a single intermediate representation for all the formats ELF/COFF/Mach-O. The native model allowed the intermediate representation to be serialized to disk too. If the intermediate representations data structures are made available to scripting languages most of all linker script script layout can be implemented by the end user. A new language also can be developed as most of the users need it and it can work on this intermediate representation.

The atom model also simplified a lot of usecases like garbage collection and having the resolve to deal just with atoms. The section model would sound simple from the outside but it it has its own challenges like separating the symbol information from section information.

The atom model also simplifies testing as there is one unique/nice way to test the core linker independent of the format.

In addition to testing, there are tools that are designed to convert ELF to COFF or viceversa, which makes lld to support these usecases by design.

Most of all embedded users want to reduce the final image size by compiling code using -ffunction-sections and -fdata-sections, which makes the atom model directly model it. Thanks to Espindola for adding support for -fno-unique-section-names which makes lld and the atom model more useful.

lld has already proven that it can link most of our llvm tools and self host with reasonable performance, I dont see why we dont want to continue with the Atom model.

Atom model also eases up dealing with LTO in general.

In summary, I would like to continue the ELF ports using the Atom model.

If a section model is being chosen to model flavors lets not mixing it up with Atom model as I can see there would be very less code sharing.

Shankar Easwaran

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation

[Joerg Sonnenberger]

On Wed, May 06, 2015 at 09:28:54PM -0500, Shankar Easwaran wrote:
> The atom model allowed lld to have a single intermediate
> representation for all the formats ELF/COFF/Mach-O. The native model
> allowed the intermediate representation to be serialized to disk
> too. If the intermediate representations data structures are made
> available to scripting languages most of all linker script script
> layout can be implemented by the end user. A new language also can
> be developed as most of the users need it and it can work on this
> intermediate representation.
>
> The atom model also simplified a lot of usecases like garbage
> collection and having the resolve to deal just with atoms. The
> section model would sound simple from the outside but it it has its
> own challenges like separating the symbol information from section
> information.

I'm sorry, but I don't get why any of this requires an atom based
representation. Saying that a single intermediate representation for
ELF/COFF on one hand and Mach-O on the other is ironic given the already
mentioned hacks on various layers. Garbage collection doesn't become
more expensive when attaching more than one symbol to each code/data
fragment. Symbol resolution doesn't change when attaching more than one
symbol to each code/data fragment. The list goes on. The single natural
advantage is that you can use a single pointer to the canonical symbol
from a code/data fragment and don't have to use a list/array. Given the
necessary and expensive hacks for splitting sections into (pseudo)
atoms, that doesn't feel like a win. So once again, what actual
advantages for ELF or COFF have been created by the atom model? Mach-O
hardly counts as it doesn't allow the flexibility of the section model
as has been discussed before.

Joerg

[Joerg Sonnenberger]

On Thu, May 07, 2015 at 10:36:45AM -0500, Shankar Easwaran wrote:
> The atom model is optimized when you compile the code with
> -ffunction-sections and -fdata-sections.

...both come with their own price and they don't always generate smaller
code.

> Once targets start having -fno-unique-section-names as the default
> the atom model looks more promising.

I don't see how that is related at all.

> In fact it simplifies the linker to not have extra
> data structures IMO.

I'm still waiting for actual examples beyond the trivial difference for
the backreference from fragments to symbols. You meanted mergeable
string sections in IRC, but that seems actually like a good example
*against* the atomic model. Having one atomic per string is quite
expensive compared just a section+offset reference with a post-merging
update pass.

[Reid Kleckner]

On Thu, May 7, 2015 at 8:36 AM, Shankar Easwaran <shan...@codeaurora.org> wrote:

The atom model is optimized when you compile the code with -ffunction-sections and -fdata-sections.

Not really, -ffunction-sections -fdata-sections gives a section-based linker the same flexibility as an atom-based linker.

In the atom model, these extra sections simply serve as a crutch to ensure that object files can be safely atomized. If you commit to the atom model, you shouldn't even need these sections, you should only need a flag that says "this section is safe for atomization". On MachO, this is what .subsections_via_symbols is for.

 

Once targets start having -fno-unique-section-names as the default the atom model looks more promising.

Why does LLD care about -fno-unique-section-names? I thought this was just an object file size optimization.

 

Everyone likes to have the image size small, and making -ffunction-sections/-fdata-sections (or) -fno-unique-section-names the default make sense and the atom model design directly has a relation to it. In fact it simplifies the linker to not have extra data structures IMO.

Again, the same is achievable in the section model by turning on these flags and enabling --gc-sections or equivalent functionality.

The only advantage I see to using the atom model for ELF and COFF is that we could dead strip object files built without -ffunction-sections -fdata-sections, which would allow us to turn these flags off in the compiler and save on object file size. I suspect the complexity of the atom model isn't worth the file size savings it offers.

[Shankar Easwaran]

On 5/7/2015 11:19 AM, Reid Kleckner wrote:
> On Thu, May 7, 2015 at 8:36 AM, Shankar Easwaran <shan...@codeaurora.org>
> wrote:
>
>> The atom model is optimized when you compile the code with
>> -ffunction-sections and -fdata-sections.
>>
> Not really, -ffunction-sections -fdata-sections gives a section-based
> linker the same flexibility as an atom-based linker.
>
> In the atom model, these extra sections simply serve as a crutch to ensure
> that object files can be safely atomized. If you commit to the atom model,
> you shouldn't even need these sections, you should only need a flag that
> says "this section is safe for atomization". On MachO, this is what
> .subsections_via_symbols is for.

We could have this flag on ELF too ? This will reducing code from third
party libraries ??

>
>> Once targets start having -fno-unique-section-names as the default the
>> atom model looks more promising.
>>
> Why does LLD care about -fno-unique-section-names? I thought this was just
> an object file size optimization.

Sorry I meant -ffunction-sections along with -fno-unique-section-names.

>
>> Everyone likes to have the image size small, and making
>> -ffunction-sections/-fdata-sections (or) -fno-unique-section-names the
>> default make sense and the atom model design directly has a relation to it.
>> In fact it simplifies the linker to not have extra data structures IMO.
>
> Again, the same is achievable in the section model by turning on these
> flags and enabling --gc-sections or equivalent functionality.
>
> The only advantage I see to using the atom model for ELF and COFF is that
> we could dead strip object files built without -ffunction-sections
> -fdata-sections, which would allow us to turn these flags off in the
> compiler and save on object file size. I suspect the complexity of the atom
> model isn't worth the file size savings it offers.
>

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation

[Shankar Easwaran]

The atom model is optimized when you compile the code with
-ffunction-sections and -fdata-sections.

Once targets start having -fno-unique-section-names as the default the
atom model looks more promising.

Everyone likes to have the image size small, and making
-ffunction-sections/-fdata-sections (or) -fno-unique-section-names the
default make sense and the atom model design directly has a relation to
it. In fact it simplifies the linker to not have extra data structures IMO.

Shankar Easwaran

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation

[Eric Christopher]

On Thu, May 7, 2015 at 9:36 AM Shankar Easwaran <shan...@codeaurora.org> wrote:

On 5/7/2015 11:19 AM, Reid Kleckner wrote:
> On Thu, May 7, 2015 at 8:36 AM, Shankar Easwaran <shan...@codeaurora.org>
> wrote:
>
>> The atom model is optimized when you compile the code with
>> -ffunction-sections and -fdata-sections.
>>
> Not really, -ffunction-sections -fdata-sections gives a section-based
> linker the same flexibility as an atom-based linker.
>
> In the atom model, these extra sections simply serve as a crutch to ensure
> that object files can be safely atomized. If you commit to the atom model,
> you shouldn't even need these sections, you should only need a flag that
> says "this section is safe for atomization". On MachO, this is what
> .subsections_via_symbols is for.
We could have this flag on ELF too ? This will reducing code from third
party libraries ??

It's really not that much unless you're up against a very hard object file input size to your linker. The total size added by -ffunction-sections is very small.

 

>
>> Once targets start having -fno-unique-section-names as the default the
>> atom model looks more promising.
>>
> Why does LLD care about -fno-unique-section-names? I thought this was just
> an object file size optimization.
Sorry I meant -ffunction-sections along with -fno-unique-section-names.
>

There's not much a reason to do this now that we have the size optimization that Rafael put in.

-eric

[Rui Ueyama]

All these points were initially advertised as advantages of the atom model, but eventually it's proved that they are not as good as we originally expected for the existing file formats at least. I became more confident on this as I work not only for the PE/COFF but also for ELF. What Joerg wrote is correct.

We (including you) have spent so much time to discuss how to model various things in the existing file formats in the atom model, which sometimes resulted in a very complex architecture, that would have otherwise been naturally and effortlessly modeled. We've wrote large amount of code to deal with the impedance mismatch between the atom model and the model that the actual file formats expect. I think it's now obvious that that was not a good trade-off if you prefer simple and clean design.

[Jim Grosbach]

Hi Rui,

Thank you for clarifying. This is very helpful.

It’s unfortunate that you’re not seeing benefits from the increased semantic knowledge the atom based model can provide. I know you’ve explored the issue thoroughly, though, so I understand why you’re wanting to move a different direction for your platform.

It’s reasonable to me to split the logic along atom based vs. section based in the LLD codebase. Ideally I’d love for that not to be so, but the practical results indicate that it is. I agree there is still worthwhile code sharing that can and should be done between the two. We’re talking about expanding the LLD project’s scope to include multiple linking models, not forking the project.

It will be important to keep the layering here such that the linking model choice is orthogonal to the file format choice. It should be possible to construct both an atom based ELF linker and a section based Mach-O linker, for example, even though the default choice for both formats is the other way around. That way different platforms with different constraints, such as what Alex talked about earlier, can make the choice of model and the choice of representation independently.

As a second step, I would very much like to see the native format brought back, if only for the atom-based model. Do you feel this is doable?

-Jim

[Rui Ueyama]

On Thu, May 7, 2015 at 12:58 PM, Jim Grosbach <gros...@apple.com> wrote:

Hi Rui,

Thank you for clarifying. This is very helpful.

It’s unfortunate that you’re not seeing benefits from the increased semantic knowledge the atom based model can provide. I know you’ve explored the issue thoroughly, though, so I understand why you’re wanting to move a different direction for your platform.

It’s reasonable to me to split the logic along atom based vs. section based in the LLD codebase. Ideally I’d love for that not to be so, but the practical results indicate that it is. I agree there is still worthwhile code sharing that can and should be done between the two. We’re talking about expanding the LLD project’s scope to include multiple linking models, not forking the project.

It will be important to keep the layering here such that the linking model choice is orthogonal to the file format choice. It should be possible to construct both an atom based ELF linker and a section based Mach-O linker, for example, even though the default choice for both formats is the other way around. That way different platforms with different constraints, such as what Alex talked about earlier, can make the choice of model and the choice of representation independently.

As a second step, I would very much like to see the native format brought back, if only for the atom-based model. Do you feel this is doable?

Yes, it's doable, but I'd really like to see this back with different unit tests because the way the feature was tested was unrealistic and hard to maintain. Previously, we tested the feature by dumping intermediate linker state to a Native file and reading it back from a file to resume processing. That was different from the expected use case, which is to use Native files as an alternative object file format. Creating a checkpoint file of the linker state is a different feature (and I guess nobody really intended to implement such feature.)

I think we need to extend yaml2obj tool to write outputs in the Native format, and use the tool to feed Native object files to the linker.

Is there anyone who wants to own the feature? Or I could just revive the code, but I'd really want to avoid doing that if that doesn't come with a good test...

[James Y Knight]

Nobody in this long thread appears to have yet explained why it's a bad idea to allow atomic fragments of code/data (whatever you want to call them: atoms, sections, who cares) to have more than one global symbol attached to them in LLD's internal representation.

That seems like it'd provide the flexibility needed for ELF without hurting MachO. If that change'd allow you to avoid splitting the linker into two-codebases-in-one, isn't that preferable?

[David Blaikie]

On Mon, May 11, 2015 at 10:56 AM, James Y Knight <jykn...@google.com> wrote:

Nobody in this long thread appears to have yet explained why it's a bad idea to allow atomic fragments of code/data (whatever you want to call them: atoms, sections, who cares) to have more than one global symbol attached to them in LLD's internal representation.

That seems like it'd provide the flexibility needed for ELF without hurting MachO. If that change'd allow you to avoid splitting the linker into two-codebases-in-one, isn't that preferable?

+1 I'd be curious to understand this too.
 

[Rui Ueyama]

If you attach two ore more symbols along with offsets to a chunk of data, it would be a pretty similar to a section. That means that if you want to do something on the atom model, now you have to treat the atoms like sections. I looks like a bad mix of the two.

On Mon, May 11, 2015 at 10:56 AM, James Y Knight <jykn...@google.com> wrote:

[David Blaikie]

On Mon, May 11, 2015 at 11:13 AM, Rui Ueyama <ru...@google.com> wrote:

If you attach two ore more symbols along with offsets to a chunk of data, it would be a pretty similar to a section. That means that if you want to do something on the atom model, now you have to treat the atoms like sections.

What do you lose/pay by having to treat the atoms like sections?
 

[Rui Ueyama]

On Mon, May 11, 2015 at 11:21 AM, David Blaikie <dbla...@gmail.com> wrote:

On Mon, May 11, 2015 at 11:13 AM, Rui Ueyama <ru...@google.com> wrote:

If you attach two ore more symbols along with offsets to a chunk of data, it would be a pretty similar to a section. That means that if you want to do something on the atom model, now you have to treat the atoms like sections.

What do you lose/pay by having to treat the atoms like sections?

I can think of a few, maybe more.

An atom model with multiple names is not as simple as before.

We still need to read all relocation tables to complete a graph as they form edges, even for duplicate COMDAT sections.

It still can't model some section-linker features, such as "select largest" COMDAT sections, because the new atom is still different from the section. (This is not an issue if we really treat atoms like sections, but that means in turn we would be going to create a Mach-O linker based on the section model.)

[Kevin Enderby]

Hello,

As the guy that came up with the “temporary” Mach-O hack to use .subsections_via_symbols a long while back I wanted throw out my thinking, though these are old thoughts before the atom concept existed.

Back in the day we needed some way to do dead code stripping at the static link editor level as code coming from the Mac OS 9 world would simply not link without this feature moving to what was to become Mac OS X (much code that was not used that had references to undefined symbols).  So we needed a quick hack and an static link editor that implemented dead code stripping asap.

I did not feel it was the linker’s place to divide up sections into smaller parts as this really should be done by the compiler that understood the language semantics it was translating.  As things like blocks of code with multiple entry points (what Fortran does), C++ constructs as explicit vs implicit Instantiation, and which blocks of code, data, exception info, and debug info to make up a group (for things like comdat).

But I felt to do this right we would have to extend the object file format and the assembly language to add support for subsections.  Then let the compiler group things in to the smallest indivisible part of the language for translation. Then symbols would be part of a specific subsection and subsections could have zero or more symbols.  Having zero symbols for some blocks and them only having references to the assembly temporary symbols that got removed I felt would be cleaner that carrying along fake symbols that must be there to divide up the section later.

The relocation entries would be per subsection and the subsection would carry the alignment directly (so it would not have to be inferred by the hack of dividing up the section).  The design would allow subsections to types (regular, literals, etc), and signature symbols (weak and non-weak) for things like comdat. 

But to do this it would have had us make extensive changes to our BSD derived Mach-O object file format that we started with.  As we had a symbol struct with only an 8 bit section number and we had another hack back in the 32-bit days to do scattered relocation entries based on 24-bits of address reference to allow references for pic code like RefSymbol - PicBaseSym.

All this could have been changed but it was deemed too aggressive and the atom model of the ld64 design prevailed as it exists today in the Mac OS X linker.

But today with clang one could see the compiler being the one deciding the smallest unit based on the target.  In the Mac OS X and iOS cases that would be the atoms, and for other targets that would be sections.  So maybe by stepping back up the compiler chain the LLD improvement plan could be better.

Some old thoughts,

Kev

[Lang Hames]

Hi Rui,

I'd like to preserve the native format, and I'm happy to own it. I'm still getting up to speed on LLD though, so it may take me a little while to improve the tooling/testing for it.

Cheers,

Lang.

[Rui Ueyama]

I'm sorry for not updating the thread -- I thought I did that before.

I started experimenting the idea by implementing a minimal linker using the section-based design with some additional simplification/optimizations. It's already able to link small programs like the LLD itself, and the performance looks indeed better (probably the LLD is too small as a benchmark, but the new one is more than 2x faster). I also believe that the code is more readable than the current COFF port.

I've just hacked it up, so it needs time to clean up. I think I can send a patch for review this week.

[Rui Ueyama]

I sent a patch to llvm-commits. You can see the code at http://reviews.llvm.org/D10036. Thanks!

[David Chisnall]

On 26 May 2015, at 20:13, Rui Ueyama <ru...@google.com> wrote:
>
> I sent a patch to llvm-commits. You can see the code at http://reviews.llvm.org/D10036. Thanks!

Why does the link not actually go where the text of it would imply, and instead bounce via some random (malicious?) third party? Do you have some malware infecting your mail client?

David

[Rui Ueyama]

David,

The link works fine with my Mac and Android. The source of the mail looks okay to me (I verified that from a different machine than the one I sent the mail). You may want to check your browser or proxy?

[Eli Bendersky]

On Wed, May 27, 2015 at 6:44 AM, David Chisnall <David.C...@cl.cam.ac.uk> wrote:

On 26 May 2015, at 20:13, Rui Ueyama <ru...@google.com> wrote:
>
> I sent a patch to llvm-commits. You can see the code at http://reviews.llvm.org/D10036. Thanks!

Why does the link not actually go where the text of it would imply, and instead bounce via some random (malicious?) third party?  Do you have some malware infecting your mail client?

David,

Checking the link in the archives [http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-May/086100.html], it goes to "http://reviews.llvm.org/D10036." -- the dot at the end is not needed and the link leads to phab sign-in from there. Removing the dot leads directly to the review. Doesn't appear to be anything malicious in there, though.

Eli

[Tobias Grosser]

On 05/27/2015 05:49 PM, Rui Ueyama wrote:
> David,
>
> The link works fine with my Mac and Android. The source of the mail
> looks okay to me (I verified that from a different machine than the one
> I sent the mail). You may want to check your browser or proxy?

Here the deHTMLified link you posted:

> On 26 May 2015, at 20:13, Rui Ueyama <ru...@google.com

> <mailto:ru...@google.com>> wrote:
> >
> > I sent a patch to llvm-commits. You can see the code athttp://reviews.llvm.org/D10036

> <https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D10036&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=oWxgKMco1iqyzHMZg3jVatTnmJ8-p1E-_oEOEjgXcFw&s=Bb50EofJm0-lxYLypIlemsdI1nLvQwlQ-cmFctxQ28w&e=>.
> Thanks!

David seems to be surprised it is going through proofpoint.com instead
of directly to llvm.org.

Best,
Tobias

[David Chisnall]

On 27 May 2015, at 16:49, Rui Ueyama <ru...@google.com> wrote:
>
> David,
>
> The link works fine with my Mac and Android. The source of the mail looks okay to me (I verified that from a different machine than the one I sent the mail). You may want to check your browser or proxy?

It’s correct in the plain-text version of the mail. The HTML MIME part contains this:

<a href=3D"https://urldefense.proofpoint.com/v2/url?u=3Dhttp-3A__reviews=
.llvm.org_D10036&d=3DAwMFaQ&c=3D8hUWFZcy2Z-Za5rBPlktOQ&r=3DMfk2qtn1LTDThVkh=
6-oGglNfMADXfJdty4_bhmuhMHA&m=3D8dYF1obzqNfZvfOxlk7H-g8VUfu1ZyS0GdcCWRkWxCk=
&s=3DRu6670O4y8SpAwlp17gVmI7BLz3mIY7gs1Irvo9iDRw&e=3D">http://reviews.llvm.=
org/D10036</a>

Apparently they’re not malicious, but I find it somewhat unnerving when the URL that I click on turns out not to be the one that the mouseover text pops up. If you feel the need to insert a redirection link, I’d very much appreciate it if you would post the full link in the text version, as well as the href. If, on the other hand, you are unaware that your computer is doing this, then I would encourage you to work out what it is and that it is not malicious.

The archives only include the plain text version, not the HTML copy, so will not see this.

[Rui Ueyama]

I sent the mail from Gmail. I checked the source using the Gmail "show original" mode (which displays a mail in plain text including headers and all MIME sections) from a different computer, but I cannot find that URL. I cannot check an email copy that the mailing list server sent back because Gmail automatically de-dup emails, which is annoying, but I think it's unlikely that my machine is infected from evidences I've seen so far. Maybe a mail transfer agent in between Gmail to you inserted the link? I'd appreciate if you can forward the mail including headers to me.

[Reid Kleckner]

I think I found the problem:

https://opia.illinois.edu/content/targeted-attack-protection-tuning

UIUC is apparently rewriting HTML links in emails to redirect through urldefense.proofpoint.com. This is visible in my version of Rui's email.

[Tim Northover]

On 27 May 2015 at 09:36, Rui Ueyama <ru...@google.com> wrote:
> I sent the mail from Gmail. I checked the source using the Gmail "show
> original" mode (which displays a mail in plain text including headers and
> all MIME sections) from a different computer, but I cannot find that URL.

I see it in GMail's "show original" (at the start of the usual
terribly-formatted HTML block). But I suspect it's the mailing list's
servers rather than your computer, Rui. This might be related:
https://opia.illinois.edu/content/targeted-attack-protection-tuning

Messing with people's messages is not great though, no matter how
well-intentioned. I bet they'd break signatures, for a start.

Tim.

[Rui Ueyama]

I agree that look like that is caused by that security measure. Why did the security software think that the benign url is malicious is still a mystery, though.

[David Blaikie]

On Wed, May 27, 2015 at 9:56 AM, Reid Kleckner <r...@google.com> wrote:

I think I found the problem:

https://opia.illinois.edu/content/targeted-attack-protection-tuning

UIUC is apparently rewriting HTML links in emails to redirect through urldefense.proofpoint.com. This is visible in my version of Rui's email.

Richard Trieu filed a bug in llvm.org/bugs that emails from the bug database are getting similar treatment, FWIW.

I don't think it's assuming maliciousness, just tracking everything most likely.
 

[David Chisnall]

On 27 May 2015, at 17:56, Reid Kleckner <r...@google.com> wrote:
>
> I think I found the problem:
> https://opia.illinois.edu/content/targeted-attack-protection-tuning
>
> UIUC is apparently rewriting HTML links in emails to redirect through urldefense.proofpoint.com. This is visible in my version of Rui's email.

Thanks for the investigation. Can we turn this off? Having emails with text containing URLs that is not the same as the link target URL is a big red flag for phishing and this is an absolutely terrible idea. This would also explain why I’ve seen a number of LLVMdev emails show up in my spam folder - I hadn’t thought to check where their links were going.

Rui: sorry for assuming that it was your fault,

[Richard Trieu]

On Wed, May 27, 2015 at 12:24 PM, David Chisnall <David.C...@cl.cam.ac.uk> wrote:

On 27 May 2015, at 17:56, Reid Kleckner <r...@google.com> wrote:
>
> I think I found the problem:
> https://opia.illinois.edu/content/targeted-attack-protection-tuning
>
> UIUC is apparently rewriting HTML links in emails to redirect through urldefense.proofpoint.com. This is visible in my version of Rui's email.

Thanks for the investigation.  Can we turn this off?  Having emails with text containing URLs that is not the same as the link target URL is a big red flag for phishing and this is an absolutely terrible idea.  This would also explain why I’ve seen a number of LLVMdev emails show up in my spam folder - I hadn’t thought to check where their links were going.

Rui: sorry for assuming that it was your fault,

David

David,

The bug https://llvm.org/bugs/show_bug.cgi?id=23643 is tracking this issue.  The URL rewriting is happening because we use the UIUC mail servers.  Tanya is contacting UIUC about getting llvm.org links whitelisted.

Richard 

[Rafael Espíndola]

Replying to the thread, not just the email since I was on vacations.

First, note that there is a nomenclature issue. A section in ELF/COFF
is closer to an atom in MachO than a MachO section IMHO.

A rose by any other name would smell as sweet, but sure as hell
creates a lot of confusion :-)

On 4 May 2015 at 18:05, Chris Lattner <clat...@apple.com> wrote:
> On May 4, 2015, at 1:16 PM, Joerg Sonnenberger <jo...@britannica.bec.de> wrote:
>> It has been said in this thread before, but I fail to see how the atom
>> model is an actual improvement over the fine grained section model. It
>> seems to be artifically restricted for no good reasons.
>
> Sections come with a huge amount of bloat and overhead that atoms do not.

No, they don't. Not on ELF for sure.

On ELF a section is just a entry into a table marking a region in the
file. The "huge amount of bloat" that people associate with sections
is actually just the extra space for the ultra large section names
".text._ZFoo....". Create multiple sections with the same name (I
implemented that) and the bloat goes away.

As has been pointed before, a section in ELF is just a better version
of what is called an Atom in lld: It is a chunk of the file that the
linker can move, but it also supports multiple symbols, which is handy
for things like making the C1 and C2 constructors share the same
address or how MSVC implement vtables+rtti.

Atoms being a distinct entity from sections (i.e., having non atomic
sections) is a necessity for MachO because it has more restrictive
sections (as Kevin was kind enough to explain).

Another way of looking at it (for understanding, I wouldn't use the
nomenclature in code) is that with this proposal lld will still be
atom based, we will just be extending atoms to support multiple
symbols. The logic for splitting sections into atoms would become

* ELF/COFF: one atom per section.
* MachO: One atom per global symbol.

And so MachO ends up with atoms that have only one symbol, but that is
just a special case.

>> This is another item that has been irritating me. While it is a very
>> laudable goal to not depend on linker scripts for the common case, not
>> having the functionality of fine grained output control is certainly a
>> problem. They are crucial for embedded developers and also at least
>> significant for anything near a system kernel.
>
> I’m not saying that the linker should eschew fine grained control, I’m saying it should dump linker scripts (and replace them with something better). Are you going to argue that linker scripts are great, or that they are what we would end up with if we weren’t driven by backwards compatibility goals?

I agree that this is a distinct issue. Linker scripts are a backward
compatibility pain. Directly using sections for ELF/COFF is *better*
than what is currently being done in lld.

As for organization, I agree with Rui's suggestion of 2 linkers in
one. One is ELF/COFF and uses sections, one is MachO and uses atoms.
Even with the split there is still enough common code that I don't
think having two repositories would help.

I don't agree that there is value in keeping the current atom on top
ELF/COFF. It just adds cost to two formats whose sections are already
flexible atoms. It also prevents optimizations like not even reading
duplicated comdats.

Last but not least, on the idea of a new object format:

Everyone that has worked on linkers or assemblers has a list of things
they don't like about the format that was being used (I do for sure).
It is entirely possible that if we get our thoughts together we can
build a better format.

Having said that, an object file format has a tremendous cost. Just
look at the pain that is maintaining support for mips' interpretation
of r_info. We have to be sure there is a genuine advantage to it
before adding a new object format to the world. To know that I think
we need to push the current formats to see how far they go.

As an analogy, imagine if people working on BFD had decided that ELF
linking was too slow or missing features and had decided to create a
new format that fit BFD better. That would have been really
unfortunate, because as gold showed the problem was not ELF, it was
the organization of BFD, but now we would probably be stuck supporting
4 formats in llvm and lld.

Once we have a linker (and MC) that is as good as it gets for ELF/COFF
and MachO we well be in a good position for discussing a new format.

Cheers,
Rafael

[Sean Silva]

I guess, looking back at Nick's comment:

"The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom."

it seems that the primary issue on the ELF/COFF side is that currently the LLVM backends are taking a finer-grained atomicity that is present inside LLVM, and losing information by converting that to a coarser-grained atomicity that is the typical "section" in ELF/COFF.

But doesn't -ffunction-sections -fdata-sections already fix this, basically?

On the Mach-O side, the issue seems to be that Mach-O's notion of section carries more hard-coded meaning than e.g. ELF, so at the very least another layer of subdivision below what Mach-O calls "section" would be needed to preserve this information; currently symbols are used as a bit of a hack as this "sub-section" layer.

So the problem seems to be that the transport format between the compiler and linker varies by platform, and each one has a different way to represent things, some can't represent everything we want to do, apparently.

BUT it sounds like at least relocatable ELF semantics can, in principle, represent everything that we can imagine an "atom-based file format"/"native format" to want to represent. Just to play devil's advocate here, let's start out with the "native format" being relocatable ELF - on *all platforms*. Relocatable object files are just a transport format between compiler and linker, after all; who cares what we use? If the alternative is a completely new format, then bootstrapping from relocatable ELF is strictly less churn/tooling cost.

People on the "atom side of the fence", what do you think? Is there anything that we cannot achieve by saying "native"="relocatable ELF"?

-- Sean Silva

[Sean Silva]

On Mon, May 4, 2015 at 7:45 AM, James Y Knight <jykn...@google.com> wrote:

And now we're against the Atom model?

I'm quite new to the llvm community, and basically unfamiliar with LLD, so maybe I'm simply uninformed. If so, I will now proceed to demonstrate that to an entire list of people. :)

I've read the doc on http://lld.llvm.org/design.html, but the list of features it says that you get with LLD/Atoms and don't get with the "old generation" of linkers that use "sections"...are all things that ELF linkers already do using sections, and do not require anything finer grained than sections. Sections in ELF objects can actually be as fine-grained as you want them to be -- just as an "Atom". Doc also says, "An atom is an indivisible chunk of code or data." -- which is also what a section is for ELF.

AFAICT, atoms in LLD are simply a restricted form of ELF sections: restricted to having a single symbol associated with them. It doesn't appear that they're actually enabling any new features that no other linker can do.

I'm not very familiar with Mach-O, but it sounds like, contrary to ELF, Mach-O files cannot be generated with one section per global object, but that Mach-O sections (at least as used by OSX) *are* expected to be subdivided/rearranged/etc, and are not atomic. Given that set of properties for the input file format, of course it makes sense that you'd want to subdivide Mach-O "sections" within the linker into smaller atomic pieces to work on them.

But for ELF, the compiler can/will output separate sections for each function/global variable, and the contents of a section should never be mangled. It can also emit multiple symbols into a single section. That an ELF section *may* contain multiple functions/globals which need to stay together is not a problem with the file format -- it's an advantage -- an additional flexibility of representation.

I gather the current model in LLD doesn't support an atomic unit with multiple symbols cleanly. And that that's the main issue that would be good to fix here.

But, rather than talking about "eliminating the atom model" -- which seems to be contentious -- maybe it would be more peaceful to just say that the desired change is to "allow atoms to have multiple global symbols associated, and have more metadata"? It appears to me that it amounts to essentially the same thing, but may not be as contentious if described that way.

If that change was made, you'd just need to know that LLD has slightly unique terminology; "ELF section" == "LLD Atom". (but "Mach-O section" turns into multiple "LLD Atom"s).

Am I wrong?

I think this is bang-on. I ended up reading this after having essentially reiterated it in different words.

-- Sean Silva

 

James

[Nick Kledzik]

On May 28, 2015, at 5:42 PM, Sean Silva <chiso...@gmail.com> wrote:

I guess, looking back at Nick's comment:

"The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom."

it seems that the primary issue on the ELF/COFF side is that currently the LLVM backends are taking a finer-grained atomicity that is present inside LLVM, and losing information by converting that to a coarser-grained atomicity that is the typical "section" in ELF/COFF.

But doesn't -ffunction-sections -fdata-sections already fix this, basically?

On the Mach-O side, the issue seems to be that Mach-O's notion of section carries more hard-coded meaning than e.g. ELF, so at the very least another layer of subdivision below what Mach-O calls "section" would be needed to preserve this information; currently symbols are used as a bit of a hack as this "sub-section" layer.

I’m not sure what you mean here.

So the problem seems to be that the transport format between the compiler and linker varies by platform, and each one has a different way to represent things, some can't represent everything we want to do, apparently.

Yes!

BUT it sounds like at least relocatable ELF semantics can, in principle, represent everything that we can imagine an "atom-based file format"/"native format" to want to represent. Just to play devil's advocate here, let's start out with the "native format" being relocatable ELF - on *all platforms*. Relocatable object files are just a transport format between compiler and linker, after all; who cares what we use? If the alternative is a completely new format, then bootstrapping from relocatable ELF is strictly less churn/tooling cost.

People on the "atom side of the fence", what do you think? Is there anything that we cannot achieve by saying "native"="relocatable ELF"?

1) Turns out .o files are written once but read many times by the linker.  Therefore, the design goal of .o files should be that they are as fast to read/parse in the linker as possible.  Slowing down the compiler to make a .o file that is faster for the linker to read is a good trade off.  This is the motivation for the native format - not that it is a universal format.

2) I think the ELF camp still thinks that linkers are “dumb”.  That they just collate .o files into executable files.  The darwin linker does a lot of processing/optimizing the content (e.g. Objective-C optimizing, dead stripping, function/data re-ordering).  This is why atom level granularity is needed.

For darwin, ELF based .o files is not interesting.  It won’t be faster, and it will take a bunch of effort to figure out how to encode all the mach-o info into ELF.  We’d rather wait for a new native format.

-Nick

[Sean Silva]

On Mon, May 4, 2015 at 12:52 PM, Chris Lattner <clat...@apple.com> wrote:

On May 1, 2015, at 12:31 PM, Rui Ueyama <ru...@google.com> wrote:

Proposal

1. Re-architect the linker based on the section model where it’s appropriate.
   
2. Stop simulating different linker semantics using the Unix model. Instead, directly implement the native behavior.

Preface: I have never personally contributed code to LLD, so don’t take anything I’m about to say too seriously.  This is not a mandate or anything, just an observation/idea.

I think that there is an alternative solution to these exact same problems.  What you’ve identified here is that there are two camps of people working on LLD, and they have conflicting goals:

- Camp A: LLD is infrastructure for the next generation of awesome linking and toolchain features, it should take advantage of how compilers work to offer new features, performance, etc without deep concern for compatibility.

- Camp B: LLD is a drop in replacement system linker (notably for COFF and ELF systems), which is best of breed and with no compromises w.r.t. that goal.

I think the problem here is that these lead to natural and inescapable tensions, and Alex summarized how Camp B has been steering LLD away from what Camp A people want.

I don't think this is correct.

The only reason we should be having a major split along Camp A and Camp B like you describe is in the face of a concrete "compatibility" feature that *absolutely cannot* be implemented without sacrificing a modular, library-based, well-architected design. That is not what this thread is about, so I don't think your split is accurate.

I think it has merely been *forgotten* that it would be useful to have an infrastructure rather than "main() in a library", or even "main() in a separate binary"!. This is the LLVM ethos (as I'm sure you know far better than I ;).

Both LLVM and Clang prove that hard problems with significant "compatibility" concerns can be tackled and top-tier in-production QoI achieved while still upholding a high standard of external reusability that allows novel uses. Given what LLVM and Clang have been able to absorb (x86 ISA? C++? MSVC inline asm?) without fundamentally destabilizing their modular design, I think that we can do a bit better with LLD before throwing in the towel and cleaving it into a "compatibility" and "shiny" part.

-- Sean Silva

 

 This isn’t bad in and of itself, because what Camp B wants is clearly and unarguably good for LLVM.  However, it is also not sufficient, and while innovation in the linker space (e.g. a new “native” object file format generated directly from compiler structures) may or may not actually “work” or be “worth it”, we won’t know unless we try, and that won’t fulfill its promise if there are compromises to Camp B.

So here’s my counterproposal: two different linkers.

Lets stop thinking about lld as one linker, and instead think of it is two different ones.  We’ll build a Camp B linker which is the best of breed section based linker.  It will support linker scripts and do everything better than any existing section based linker.  The first step of this is to do what Rui proposes and rip atoms out of the model.

We will also build a no-holds-barred awesome atom based linker that takes advantage of everything it can from LLVM’s architecture to enable innovative new tools without worrying too much about backwards compatibility.

These two linkers should share whatever code makes sense, but also shouldn’t try to share code that doesn’t make sense.  The split between the semantic model of sections vs atoms seems like a very natural one to me.

One question is: does it make sense for these to live in the same lld subproject, or be split into two different subprojects?  I think the answer to that question is driven from whether there is shared code common between the two linkers that doesn’t make sense to sink down to the llvm subproject itself.

What do you think?

-Chris

[Sean Silva]

On Thu, May 28, 2015 at 6:25 PM, Nick Kledzik <kle...@apple.com> wrote:

On May 28, 2015, at 5:42 PM, Sean Silva <chiso...@gmail.com> wrote:

I guess, looking back at Nick's comment:

"The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom."

it seems that the primary issue on the ELF/COFF side is that currently the LLVM backends are taking a finer-grained atomicity that is present inside LLVM, and losing information by converting that to a coarser-grained atomicity that is the typical "section" in ELF/COFF.

But doesn't -ffunction-sections -fdata-sections already fix this, basically?

On the Mach-O side, the issue seems to be that Mach-O's notion of section carries more hard-coded meaning than e.g. ELF, so at the very least another layer of subdivision below what Mach-O calls "section" would be needed to preserve this information; currently symbols are used as a bit of a hack as this "sub-section" layer.

I’m not sure what you mean here.

So the problem seems to be that the transport format between the compiler and linker varies by platform, and each one has a different way to represent things, some can't represent everything we want to do, apparently.

Yes!

BUT it sounds like at least relocatable ELF semantics can, in principle, represent everything that we can imagine an "atom-based file format"/"native format" to want to represent. Just to play devil's advocate here, let's start out with the "native format" being relocatable ELF - on *all platforms*. Relocatable object files are just a transport format between compiler and linker, after all; who cares what we use? If the alternative is a completely new format, then bootstrapping from relocatable ELF is strictly less churn/tooling cost.

People on the "atom side of the fence", what do you think? Is there anything that we cannot achieve by saying "native"="relocatable ELF"?

1) Turns out .o files are written once but read many times by the linker.  Therefore, the design goal of .o files should be that they are as fast to read/parse in the linker as possible.  Slowing down the compiler to make a .o file that is faster for the linker to read is a good trade off.  This is the motivation for the native format - not that it is a universal format.

Whenever this has come up, Rafael has always told me that (at least in the context of ELF) that the current file format isn't a problem in this regard. Maybe you guys should talk?

 

2) I think the ELF camp still thinks that linkers are “dumb”.  That they just collate .o files into executable files.  The darwin linker does a lot of processing/optimizing the content (e.g. Objective-C optimizing, dead stripping, function/data re-ordering).  This is why atom level granularity is needed.

As has been mentioned elsewhere in the thread, ELF is able to represent atoms (in fact, something more general). So I guess this just leaves us with that you think that current object file formats are too slow to read? That begs for some numbers.

 

For darwin, ELF based .o files is not interesting.  It won’t be faster, and it will take a bunch of effort to figure out how to encode all the mach-o info into ELF.

I was playing devil's advocate with the concrete ELF suggestion, but I think that it wouldn't be really any different amount of effort vs encoding it in a "native" format. I mean, in the worst case you can just make a custom section in the ELF file and put whatever you want in there, while keeping the rest of the file structure for the bulk of the object. ELF has very much a "bag of bytes" approach, so layering any semantics on top should be pretty easy.

-- Sean Silva

[Rui Ueyama]

On Thu, May 28, 2015 at 6:25 PM, Nick Kledzik <kle...@apple.com> wrote:

On May 28, 2015, at 5:42 PM, Sean Silva <chiso...@gmail.com> wrote:

I guess, looking back at Nick's comment:

"The atom model is a good fit for the llvm compiler model for all architectures.  There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom."

it seems that the primary issue on the ELF/COFF side is that currently the LLVM backends are taking a finer-grained atomicity that is present inside LLVM, and losing information by converting that to a coarser-grained atomicity that is the typical "section" in ELF/COFF.

But doesn't -ffunction-sections -fdata-sections already fix this, basically?

On the Mach-O side, the issue seems to be that Mach-O's notion of section carries more hard-coded meaning than e.g. ELF, so at the very least another layer of subdivision below what Mach-O calls "section" would be needed to preserve this information; currently symbols are used as a bit of a hack as this "sub-section" layer.

I’m not sure what you mean here.

So the problem seems to be that the transport format between the compiler and linker varies by platform, and each one has a different way to represent things, some can't represent everything we want to do, apparently.

Yes!

BUT it sounds like at least relocatable ELF semantics can, in principle, represent everything that we can imagine an "atom-based file format"/"native format" to want to represent. Just to play devil's advocate here, let's start out with the "native format" being relocatable ELF - on *all platforms*. Relocatable object files are just a transport format between compiler and linker, after all; who cares what we use? If the alternative is a completely new format, then bootstrapping from relocatable ELF is strictly less churn/tooling cost.

People on the "atom side of the fence", what do you think? Is there anything that we cannot achieve by saying "native"="relocatable ELF"?

1) Turns out .o files are written once but read many times by the linker.  Therefore, the design goal of .o files should be that they are as fast to read/parse in the linker as possible.  Slowing down the compiler to make a .o file that is faster for the linker to read is a good trade off.  This is the motivation for the native format - not that it is a universal format.

I don't think that switching from ELF to something new can make linkers significantly faster. We need to handle ELF files carefully not to waste time on initial load, but if you do, reading data required for symbol resolution from ELF file should be satisfactory fast (I did that for COFF -- the current "atom-based ELF" linker is doing too much things in an initial load, like read all relocation tables, splitting indivisble chunk of data and connect them with "indivisible" edges, etc.) Looks like we read symbol table pretty quickly in the new implementation, and the bottleneck of it is now the time to insert symbols into the symbol hash table -- which you cannot make faster by changing object file format.

Speaking of the performance, if I want to make a significant difference, I'd focus on introducing new symbol resolution semantics. Especially, the Unix linker semantics is pretty bad for performance because we have to visit files one by one serially and possibly repeatedly. It's not only bad for parallelism but also for a single-thread case because it increase size of data to be processed. This is I believe the true bottleneck of Unix linkers. Tackling that problem seems to be most important to me, and "ELF as a file format is slow" is still an unproved thing to me.

 

2) I think the ELF camp still thinks that linkers are “dumb”.  That they just collate .o files into executable files.  The darwin linker does a lot of processing/optimizing the content (e.g. Objective-C optimizing, dead stripping, function/data re-ordering).  This is why atom level granularity is needed.

I think that all these things are doable (and are being done) using -ffunction-sections.

 

For darwin, ELF based .o files is not interesting.  It won’t be faster, and it will take a bunch of effort to figure out how to encode all the mach-o info into ELF.  We’d rather wait for a new native format.

-Nick

[Rui Ueyama]

I want to make it clear that I didn't (at least intend to) compromise flexibility or beauty of design with short-term performance gain. I was trying to do simple things in a simple way for both humans and computers, and I believe I did that fairly well.  I'd even argue that the new design is cleaner and more expressive than before, because the "atom" model is in some part too detailed and restrictive on how to represent data and relations between symbols, particularly how to represent relocations. It also lacked capability of representing indivisible memory areas having multiple names.

After I wrote up the first patch, I realized that the goal of the code is somewhat similar to what the atom model aims to achieve, with some differences. I assume that you have read the readme file for the new port. The differences are

 -  An atom has only one name, but the new "chunk" can have one or more symbols referring that. But the actual difference is that chunks are agnostic of symbols referring them in the new design. I have separated actual data from symbols to get more flexibility. And that flexibility enabled me to achieve better performance by writing more abstract code which reads less data.

 - In the atom model, we have detailed information about relocations, including relocation target, offset, etc, for each atom. In the new design, we don't have them. Instead, we have just a set of symbols for each chunk that needs to be resolved to include that input chunk properly. This is more abstract and flexible than the existing design.

- The atom model reads too much data from files prematurely to construct a complete graph, while the new design avoided that. This is partly an implementation's issue, but partly unavoidable, because we actually needed to build more complex data structure.

- And this might be stemmed from the implementation and not from the model itself, but the thing is that it's hard to write code for the atom model because their data types have too much detailed relations with other types. For example, any atom in the model has to have a "file" that an atom was created from. This makes it hard to append linker-generated data to output which don't have a source file (we ended up having a notion of "virtual input file" that doesn't do anything meaningful itself.). Another example is that, if you want to create a symbol on-demand, you've got to create a "virtual archive" file that returns a "virtual file" containing one "virtual atom" when the archive file is asked for that symbol. In the new design, it can be expressed in one line of code instead of multiple class definitions and object juggling. Also, because relocations are explicitly represented as "references" in the atom model, we've got to create platform-specific relocation objects even for linker-generated data if it refers some other symbols, and let a platform-specific relocation function to consume that data to apply relocations. That's less abstracted than the new design, in which all classes but the actual data type needs to know about relocations are agnostic about how relocations are represented and how to actually apply them.

Besides them, I'd say from my experiences of working on the atom model, the new model's ability is not that different from the atom model. They are different, there are pros and cons, and I don't agree that the atom model is more flexible or conceptually better.

[Rafael Espíndola]

> Speaking of the performance, if I want to make a significant difference, I'd
> focus on introducing new symbol resolution semantics. Especially, the Unix
> linker semantics is pretty bad for performance because we have to visit
> files one by one serially and possibly repeatedly. It's not only bad for
> parallelism but also for a single-thread case because it increase size of
> data to be processed. This is I believe the true bottleneck of Unix linkers.
> Tackling that problem seems to be most important to me, and "ELF as a file
> format is slow" is still an unproved thing to me.

It is more than unproven. It is proven wrong.

Short of your new COFF linker, gold is ELF only and the fastest linker around.

We have a badly designed ELF linker. That is hardly ELF's fault.

Cheers,
Rafael

[Rafael Espíndola]

> 2) I think the ELF camp still thinks that linkers are “dumb”. That they
> just collate .o files into executable files. The darwin linker does a lot
> of processing/optimizing the content (e.g. Objective-C optimizing, dead
> stripping, function/data re-ordering). This is why atom level granularity
> is needed.

If there is any linker in here that is dumb that is the old lld. It
reads parts of the file it doesn't need, it can't optimize exception
frames, --gc-section is not working, strings are not tail merged and
it takes about 2x the cpu time of gold even with gold doing all those
things.

Rui's new design finally given us the opportunity of making an useful
linker out of lld.

[Chandler Carruth]

On Fri, May 29, 2015 at 6:46 AM Rafael Espíndola <rafael.e...@gmail.com> wrote:

> 2) I think the ELF camp still thinks that linkers are “dumb”.  That they
> just collate .o files into executable files.  The darwin linker does a lot
> of processing/optimizing the content (e.g. Objective-C optimizing, dead
> stripping, function/data re-ordering).  This is why atom level granularity
> is needed.

If there is any linker in here that is dumb that is the old lld.

Rafael, I know you're trying to make a point here, but I think this really pushes into name calling and putting down of work.

Every project starts off slow and without features. I'm not trying to push one way or the other on the topic of this thread, I just think you should take a more charitable tone when describing the existing work that your colleagues in the open source community have done. Lots of lots of folks worked really hard on LLD up until now, and I think it is important to be more respectful of the hard work they put in. Even when things don't work out, or the code ends up not being as good as we need it to be, I want to make sure we show appropriate respect for the work that went into it. We should provide a technical critique, and try to make sure it isn't too easily misinterpreted as a critique of intentions, etc.

-Chandler

[Sean Silva]

On Fri, May 29, 2015 at 1:14 AM, Rui Ueyama <ru...@google.com> wrote:

I want to make it clear that I didn't (at least intend to) compromise flexibility or beauty of design with short-term performance gain. I was trying to do simple things in a simple way for both humans and computers, and I believe I did that fairly well.  I'd even argue that the new design is cleaner and more expressive than before, because the "atom" model is in some part too detailed and restrictive on how to represent data and relations between symbols, particularly how to represent relocations. It also lacked capability of representing indivisible memory areas having multiple names.

After I wrote up the first patch, I realized that the goal of the code is somewhat similar to what the atom model aims to achieve, with some differences. I assume that you have read the readme file for the new port. The differences are

 -  An atom has only one name, but the new "chunk" can have one or more symbols referring that. But the actual difference is that chunks are agnostic of symbols referring them in the new design. I have separated actual data from symbols to get more flexibility. And that flexibility enabled me to achieve better performance by writing more abstract code which reads less data.

 - In the atom model, we have detailed information about relocations, including relocation target, offset, etc, for each atom. In the new design, we don't have them. Instead, we have just a set of symbols for each chunk that needs to be resolved to include that input chunk properly. This is more abstract and flexible than the existing design.

- The atom model reads too much data from files prematurely to construct a complete graph, while the new design avoided that. This is partly an implementation's issue, but partly unavoidable, because we actually needed to build more complex data structure.

- And this might be stemmed from the implementation and not from the model itself, but the thing is that it's hard to write code for the atom model because their data types have too much detailed relations with other types. For example, any atom in the model has to have a "file" that an atom was created from. This makes it hard to append linker-generated data to output which don't have a source file (we ended up having a notion of "virtual input file" that doesn't do anything meaningful itself.). Another example is that, if you want to create a symbol on-demand, you've got to create a "virtual archive" file that returns a "virtual file" containing one "virtual atom" when the archive file is asked for that symbol. In the new design, it can be expressed in one line of code instead of multiple class definitions and object juggling. Also, because relocations are explicitly represented as "references" in the atom model, we've got to create platform-specific relocation objects even for linker-generated data if it refers some other symbols, and let a platform-specific relocation function to consume that data to apply relocations. That's less abstracted than the new design, in which all classes but the actual data type needs to know about relocations are agnostic about how relocations are represented and how to actually apply them.

These all sound like things that just indicate "we have some refactoring to do", just like Duncan did for debug metadata, or David is doing for the opaque pointer type, or how the Type system has been changed over the years, or how clang's template parsing is changed to be compatible with weird MSVC behavior. Is there something about the current situation with LLD that made you think that refactoring was hopeless and required a rewrite? If what we currently have doesn't fit our use cases, why not just fix it?

Besides them, I'd say from my experiences of working on the atom model, the new model's ability is not that different from the atom model. They are different, there are pros and cons, and I don't agree that the atom model is more flexible or conceptually better.

I don't understand this focus on "the atom model". "the atom model" is not any particular thing. We can generalize the meaning of atom, we can make it more narrow, we can remove responsibilities from Atom, we can add responsibilities to Atom, we can do whatever is needed. As you yourself admit, the "new model" is not that different from "the atom model". Think of "the atom model" like SSA. LLVM IR is SSA; there is a very large amount of freedom to decide on the exact design within that scope. "the atom model" AFAICT just means that a core abstraction inside the linker is the notion of an indivisible chunk. Our current design might need to be changed, but starting from scratch only to arrive at the same basic idea but now having to effectively maintain two codebases doesn't seem worth it.

A lot of the issue here is that we are falsely distinguishing "section-based" and "atom-based". A suitable generalization of the notion of "indivisible chunks" and what you can do with them covers both cases, but traditional usage of sections makes the "indivisible chunks" be a lot larger (and loses more information in doing so). But as -ffunction-sections/-fdata-sections shows, there is not really any fundamental difference.

-- Sean Silva

[Tim Northover]

On 28 May 2015 at 18:25, Nick Kledzik <kle...@apple.com> wrote:
> For darwin, ELF based .o files is not interesting. It won’t be faster, and
> it will take a bunch of effort to figure out how to encode all the mach-o
> info into ELF. We’d rather wait for a new native format.

Practically, you're almost certainly right (in terms of development
costs to a temporary solution). But from a personal level I would much
prefer an ELF-based Darwin to the status quo. I think Darwin suffers
greatly from being based on MachO, which isn't something I could say
about Linux/ELF. There are far too many implicit contracts between
tools.

> We’d rather wait for a new native format.

Assuming a good one comes along.

Tim.

[Tim Northover]

On 29 May 2015 at 18:48, Tim Northover <t.p.no...@gmail.com> wrote:
>I think Darwin suffers
> greatly from being based on MachO, which isn't something I could say
> about Linux/ELF.

P.S. This is by no means intended to belittle the work of the people
who've created MachO in its current form. Given what you started with
(an object format with *16*(!!!!!) possible relocations, for example)
you've done miracles. But the end result is not optimal, and probably
a guide for the rest of us on what to avoid.

[Rui Ueyama]

On Fri, May 29, 2015 at 6:01 PM, Sean Silva <chiso...@gmail.com> wrote:

On Fri, May 29, 2015 at 1:14 AM, Rui Ueyama <ru...@google.com> wrote:

I want to make it clear that I didn't (at least intend to) compromise flexibility or beauty of design with short-term performance gain. I was trying to do simple things in a simple way for both humans and computers, and I believe I did that fairly well.  I'd even argue that the new design is cleaner and more expressive than before, because the "atom" model is in some part too detailed and restrictive on how to represent data and relations between symbols, particularly how to represent relocations. It also lacked capability of representing indivisible memory areas having multiple names.

After I wrote up the first patch, I realized that the goal of the code is somewhat similar to what the atom model aims to achieve, with some differences. I assume that you have read the readme file for the new port. The differences are

 -  An atom has only one name, but the new "chunk" can have one or more symbols referring that. But the actual difference is that chunks are agnostic of symbols referring them in the new design. I have separated actual data from symbols to get more flexibility. And that flexibility enabled me to achieve better performance by writing more abstract code which reads less data.

 - In the atom model, we have detailed information about relocations, including relocation target, offset, etc, for each atom. In the new design, we don't have them. Instead, we have just a set of symbols for each chunk that needs to be resolved to include that input chunk properly. This is more abstract and flexible than the existing design.

- The atom model reads too much data from files prematurely to construct a complete graph, while the new design avoided that. This is partly an implementation's issue, but partly unavoidable, because we actually needed to build more complex data structure.

- And this might be stemmed from the implementation and not from the model itself, but the thing is that it's hard to write code for the atom model because their data types have too much detailed relations with other types. For example, any atom in the model has to have a "file" that an atom was created from. This makes it hard to append linker-generated data to output which don't have a source file (we ended up having a notion of "virtual input file" that doesn't do anything meaningful itself.). Another example is that, if you want to create a symbol on-demand, you've got to create a "virtual archive" file that returns a "virtual file" containing one "virtual atom" when the archive file is asked for that symbol. In the new design, it can be expressed in one line of code instead of multiple class definitions and object juggling. Also, because relocations are explicitly represented as "references" in the atom model, we've got to create platform-specific relocation objects even for linker-generated data if it refers some other symbols, and let a platform-specific relocation function to consume that data to apply relocations. That's less abstracted than the new design, in which all classes but the actual data type needs to know about relocations are agnostic about how relocations are represented and how to actually apply them.

These all sound like things that just indicate "we have some refactoring to do", just like Duncan did for debug metadata, or David is doing for the opaque pointer type, or how the Type system has been changed over the years, or how clang's template parsing is changed to be compatible with weird MSVC behavior. Is there something about the current situation with LLD that made you think that refactoring was hopeless and required a rewrite? If what we currently have doesn't fit our use cases, why not just fix it?

I don't think these points indicate a need of refactoring. Or the meaning of refactoring is too broad. "Atom has only one name" is a baked in assumption everywhere (like "in SSA variables are assigned only once"). "Atom has data" is another assumption. "Relocations are represented as graph edges" is yet another. Or "everything is represented using atoms and references". These design choices are made at the beginning, and they are everywhere. If you change them, you have to update virtually all code. Then what's the point of refactoring compared to creating a new foundation + move code on it? I found that the former is difficult to do.

I understand what you are saying, because as you might have noticed, I'm probably the person who spent one's time most on refactoring it to do what you are saying. I wanted to make it more readable, easy to add features, and run faster. I worked actually really hard. Although I partly succeeded, I was disappointed to myself because of a (lack of) progress. After all, I had to conclude that that was not going to work --  they are so different that it's not reasonable to spend time on that direction. A better approach is to set a new foundation and move existing code to them, instead of doing rework in-place. It may also worth mentioning that the new approach worked well. I made up a self-hosting linker only in two weeks, which does support dead-stripping and is more than 4x faster.

Besides them, I'd say from my experiences of working on the atom model, the new model's ability is not that different from the atom model. They are different, there are pros and cons, and I don't agree that the atom model is more flexible or conceptually better.

I don't understand this focus on "the atom model". "the atom model" is not any particular thing. We can generalize the meaning of atom, we can make it more narrow, we can remove responsibilities from Atom, we can add responsibilities to Atom, we can do whatever is needed. As you yourself admit, the "new model" is not that different from "the atom model". Think of "the atom model" like SSA. LLVM IR is SSA; there is a very large amount of freedom to decide on the exact design within that scope. "the atom model" AFAICT just means that a core abstraction inside the linker is the notion of an indivisible chunk. Our current design might need to be changed, but starting from scratch only to arrive at the same basic idea but now having to effectively maintain two codebases doesn't seem worth it.

Large part of the difficulties in development of the current LLD comes from over-generalizataion to share code between pretty much different file formats. My observation is that we ended up having to write large amount of code to share little core even which doesn't really fit well any platform (an example is the virtual archive file I mentioned above -- that was invented to hide platform-specific atom creation behind something platform-neutral stuff, and because archive files are supported by three platforms, they are chosen.) Different things are different, we need to get the right balance. I don't think that the current balance is not right.

[James Y Knight]

On May 29, 2015, at 10:08 PM, Rui Ueyama <ru...@google.com> wrote:
> Large part of the difficulties in development of the current LLD comes from over-generalizataion to share code between pretty much different file formats.

ISTM the problem that's been described isn't that code is shared between file formats, but that an internal representation was chosen based on what MachO required, which in the end turned out to be unsuitable for representing the greater generality allowed by the other two file formats.

You state that the goal is to use this new model for ELF too, assuming it proves itself worthy. Will ELF and COFF not share most of the core of the code at that point?

And once COFF and ELF are taken care of, do you not think the new model will be suitable for MachO, too? It seems to me that it ought to be able to handle MachO's needs just fine, with a suitable division of MachO sections into "Chunk"s.

Perhaps once everything is said and done, lld can once again have a single core model. I think that may be what Sean was trying to get at -- not that it's wrong to create a new model as a base, but that the expectation should be that new model will be _the_ model used in LLD, not a second model to be kept permanently alongside the current "single-symbol-per-atom" model, which has been shown insufficient.

[Sean Silva]

On Fri, May 29, 2015 at 8:29 PM, James Y Knight <jykn...@google.com> wrote:

On May 29, 2015, at 10:08 PM, Rui Ueyama <ru...@google.com> wrote:
> Large part of the difficulties in development of the current LLD comes from over-generalizataion to share code between pretty much different file formats.

ISTM the problem that's been described isn't that code is shared between file formats, but that an internal representation was chosen based on what MachO required, which in the end turned out to be unsuitable for representing the greater generality allowed by the other two file formats.

You state that the goal is to use this new model for ELF too, assuming it proves itself worthy. Will ELF and COFF not share most of the core of the code at that point?

And once COFF and ELF are taken care of, do you not think the new model will be suitable for MachO, too? It seems to me that it ought to be able to handle MachO's needs just fine, with a suitable division of MachO sections into "Chunk"s.

Perhaps once everything is said and done, lld can once again have a single core model. I think that may be what Sean was trying to get at -- not that it's wrong to create a new model as a base, but that the expectation should be that new model will be _the_ model used in LLD, not a second model to be kept permanently alongside the current "single-symbol-per-atom" model, which has been shown insufficient.

I couldn't have said it better myself.

Looking at the bigger picture, without some sort of commonality factored across all 3 formats in LLD, it is very difficult for the LLVM project to deliver useful innovations consistently across platforms. Without a common model, we are limited to a patchwork of platform-specific hacks; with a common model, we can think about new features at a higher level and deliver them consistently.

The situation is very analogous to the reason why it is a good idea to have the LLVM IR in the middle-end. The LLVM IR is not target-agnostic; but the target-specific aspects are managed in more-or-less controlled fashion that allows thinking about certain things at a higher level.

 

-- Sean Silva 

[Sean Silva]

On Fri, May 29, 2015 at 7:08 PM, Rui Ueyama <ru...@google.com> wrote:

On Fri, May 29, 2015 at 6:01 PM, Sean Silva <chiso...@gmail.com> wrote:

On Fri, May 29, 2015 at 1:14 AM, Rui Ueyama <ru...@google.com> wrote:

I want to make it clear that I didn't (at least intend to) compromise flexibility or beauty of design with short-term performance gain. I was trying to do simple things in a simple way for both humans and computers, and I believe I did that fairly well.  I'd even argue that the new design is cleaner and more expressive than before, because the "atom" model is in some part too detailed and restrictive on how to represent data and relations between symbols, particularly how to represent relocations. It also lacked capability of representing indivisible memory areas having multiple names.

After I wrote up the first patch, I realized that the goal of the code is somewhat similar to what the atom model aims to achieve, with some differences. I assume that you have read the readme file for the new port. The differences are

 -  An atom has only one name, but the new "chunk" can have one or more symbols referring that. But the actual difference is that chunks are agnostic of symbols referring them in the new design. I have separated actual data from symbols to get more flexibility. And that flexibility enabled me to achieve better performance by writing more abstract code which reads less data.

 - In the atom model, we have detailed information about relocations, including relocation target, offset, etc, for each atom. In the new design, we don't have them. Instead, we have just a set of symbols for each chunk that needs to be resolved to include that input chunk properly. This is more abstract and flexible than the existing design.

- The atom model reads too much data from files prematurely to construct a complete graph, while the new design avoided that. This is partly an implementation's issue, but partly unavoidable, because we actually needed to build more complex data structure.

- And this might be stemmed from the implementation and not from the model itself, but the thing is that it's hard to write code for the atom model because their data types have too much detailed relations with other types. For example, any atom in the model has to have a "file" that an atom was created from. This makes it hard to append linker-generated data to output which don't have a source file (we ended up having a notion of "virtual input file" that doesn't do anything meaningful itself.). Another example is that, if you want to create a symbol on-demand, you've got to create a "virtual archive" file that returns a "virtual file" containing one "virtual atom" when the archive file is asked for that symbol. In the new design, it can be expressed in one line of code instead of multiple class definitions and object juggling. Also, because relocations are explicitly represented as "references" in the atom model, we've got to create platform-specific relocation objects even for linker-generated data if it refers some other symbols, and let a platform-specific relocation function to consume that data to apply relocations. That's less abstracted than the new design, in which all classes but the actual data type needs to know about relocations are agnostic about how relocations are represented and how to actually apply them.

These all sound like things that just indicate "we have some refactoring to do", just like Duncan did for debug metadata, or David is doing for the opaque pointer type, or how the Type system has been changed over the years, or how clang's template parsing is changed to be compatible with weird MSVC behavior. Is there something about the current situation with LLD that made you think that refactoring was hopeless and required a rewrite? If what we currently have doesn't fit our use cases, why not just fix it?

I don't think these points indicate a need of refactoring. Or the meaning of refactoring is too broad. "Atom has only one name" is a baked in assumption everywhere (like "in SSA variables are assigned only once"). "Atom has data" is another assumption. "Relocations are represented as graph edges" is yet another. Or "everything is represented using atoms and references". These design choices are made at the beginning, and they are everywhere. If you change them, you have to update virtually all code. Then what's the point of refactoring compared to creating a new foundation + move code on it? I found that the former is difficult to do.

One of the standard reasons to prefer refactoring, even though it appears to take longer or be more difficult, is that it allows you to always keep all tests green. It is very easy for things to slip through the cracks and not promptly return to being green on a "from-scratch" version. This ultimately turns into bug reports later and the feature needs to be reimplemented; the apparent simplicity of the "from-scratch" version can disappear very rapidly.

In the refactoring approach you are forced to incorporate a holistic understanding of the necessary features into your simplification efforts, since the tests keep you from accidentally disregarding necessary features.

It is very easy to accidentally buy simplicity at the cost of losing features; if you eventually need the features back then the apparent simplicity is an illusion.

-- Sean Silva

[Rui Ueyama]

I think many common parts are already factored out as libObject or libLTO, so I'm not too worried about that. We should factor out even more and make linker smaller.

By common model, do you mean we should have a set of common base classes for all three linkers? I'm not sure if we can do this. I'm not against that, though. It feels to me that "having a common model makes things easier" is a unproved hypothesis, and I presented many counter examples already. At least I believe we can agree that the current model doesn't work as the one. Maybe the new one can be the one, but we are not sure yet. I hope it sets a common model, but I'm also okay with sharing less code if it makes sense overall. We need to experiment. The first try to set a common model didn't seem successful, at least.

Did you read the existing code and the new one? In general terms, I'd totally agree with you. What you are saying is a good engineering practice. However, as I said, I tried hard to refactor that already for months or maybe over a year continually and came to this kind of depressing conclusion. If you hack on the existing LLD and the new one, I believe you would understand the point.

(One interesting story would be that I tried to add LTO to LLD a few months ago but couldn't make it because it took too much time because of the complexity (and that was the final push to make me think that was not going to work), and then Peter came in and wrote up the first LTO patch for the new COFF linker pretty quickly. Peter knows far more than me about LTO for sure, but still it means something.)

I believe we should be careful about applying compiler's analogy to linkers. They are pretty different.

[Colin LeMahieu]

I don’t have a specific recommendation on LLD since I know little about the details though I’ll voice general support of incremental refactor over anything else.  Rewrites are seductive though I’ve seldom seen them come to successful conclusion.

 

On the flip side let’s not fall in to the trap of forcing an abstraction if it doesn’t fit.  Abstract the algorithms that are common and don’t try to abstract things that are fundamentally different and are not interchangeable between formats.

 

Hopefully these vague comments are helpful in some way J

[Gleb Popov]

I remember something called MCLinker back in times when LLD was starting. What happened to this project? Sorry if it's absolutely unrelated to the topic.

[Xinliang David Li]

One of the standard reasons to prefer refactoring, even though it appears to take longer or be more difficult, is that it allows you to always keep all tests green. It is very easy for things to slip through the cracks and not promptly return to being green on a "from-scratch" version. This ultimately turns into bug reports later and the feature needs to be reimplemented; the apparent simplicity of the "from-scratch" version can disappear very rapidly.

Hmm, why can't the from-scratch version use existing tests to make sure major features are not regressed?

Refactoring requires a good foundation. If the foundation is broken, rewriting is more preferred. There are many successful stories of complete rewrite.

 

In the refactoring approach you are forced to incorporate a holistic understanding of the necessary features into your simplification efforts, since the tests keep you from accidentally disregarding necessary features.

 

Features are protected with good tests. This has nothing to do with the approach taken.

It is very easy to accidentally buy simplicity at the cost of losing features; if you eventually need the features back then the apparent simplicity is an illusion.

It is probably not quite useful debating in abstract. Rui already has the initial implementation ready which shows very promising results ...

just my 2c.

David

[Simon Atanasyan]

It's alive and updated regularly but is not under very active
development though. It supports ELF AArch64/ARM/Hexagon/Mips/X86
targets and some cool features like identical code folding. By the way
it operates on "Fragments" where the Fragment is the minimal linking
unit. This concept is similar to Chunk.

https://github.com/mclinker/mclinker

--
Simon Atanasyan

[Reid Kleckner]

On Fri, May 29, 2015 at 11:54 PM, Xinliang David Li <xinli...@gmail.com> wrote:

One of the standard reasons to prefer refactoring, even though it appears to take longer or be more difficult, is that it allows you to always keep all tests green. It is very easy for things to slip through the cracks and not promptly return to being green on a "from-scratch" version. This ultimately turns into bug reports later and the feature needs to be reimplemented; the apparent simplicity of the "from-scratch" version can disappear very rapidly.

Hmm, why can't the from-scratch version use existing tests to make sure major features are not regressed?

Based on what I've seen, Rui started with the most minimal PE COFF linker that could link against system DLLs and is porting the old tests as new functionality is added. The old tests serve as a checklist of features to implement, and eventually everything will be ported without many regressions. Given that this is essentially a rewrite and not a refactor, I think that's probably the way to go.

 

Refactoring requires a good foundation. If the foundation is broken, rewriting is more preferred. There are many successful stories of complete rewrite.

Looking at the progress that Rui is making, I think this is going to be one of those situations where the rewrite is ultimately successful.