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.
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.
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.
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.
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.
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?
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...
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?
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?
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.
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?
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.)
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.
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.
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.
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?
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?
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 "Login; -- 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.
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?