[PROPOSAL] ELF safe/unsafe sections

Hi,

Currently lld ties up all atoms in a section for ELF together. This proposal just breaks it by handling it differently.

This requires NO ELF ABI changes.

Definitions :-

A section is not considered safe if there is some code that appears to be present between function boundaries (or) optimizes sections to place data at the end or beginning of a section (that contains no symbol).

A section is considered safe if symbols contained within the section have been associated with their appropriate sizes and there is no data present between function boundaries.

Examples of safe sections are, code generated by compilers.

Examples of unsafe sections are, hand written assembly code.

Changes Needed :-

The change that I am trying to propose is the compiler emits a section, called (.safe_sections) that contains section indices on what sections are safe.

The section would have a SHF_EXCLUDE flag, to prevent other linkers from consuming this section and making it to the output file.

Data structure for this :-

.safe_sections

... ...

Advantages
There are advantages that the atoms within a safe section could just be allocated in the output file which means better output file layout, and Better performance!

This would also result in more atoms getting gc’ed.

a) looking at profile information
b) taking a order file

Changes needed in the assembler

a) add an additional flag in the section for people writing assembly code, to mark a section safe or unsafe.

Changes needed in lld

a) Read the safe section if its present in the object file
b) Tie atoms together within a section if the section is not safe

Thanks

Shankar Easwaran

I think I share the goal with you to make the foundation for better dead-strip, so thank you for suggesting. I’m not sure if marking a section as a whole as “safe” or “unsafe” is the best approach, though. Some comments.

  • If the compiler generated code is always “safe”, and if we can distinguish it from hand-written assembly code by checking if there’s a gap between symbols, can we just assume a section with no gap is always “safe”?
  • “Safeness” is not an attribute of the section but of the symbol, I think. The symbol is “safe” if there’s no direct reference to the symbol data. All references should go through relocations. A section may contain both “safe” and “unsafe” symbols.
  • How about making the compiler to create a new section for each “safe” atom, as it does for inline functions?

I think I share the goal with you to make the foundation for better
dead-strip, so thank you for suggesting. I'm not sure if marking a section
as a whole as "safe" or "unsafe" is the best approach, though. Some
comments.

  - If the compiler generated code is always "safe", and if we can
distinguish it from hand-written assembly code by checking if there's a gap
between symbols, can we just assume a section with no gap is always "safe"?

Gaps could just be caused due to alignment, but the code may be safe, which the compiler knows very well.

  - "Safeness" is not an attribute of the section but of the symbol, I
think. The symbol is "safe" if there's no direct reference to the symbol
data. All references should go through relocations. A section may contain
both "safe" and "unsafe" symbols.

Sections contain symbols. In the context of ELF, marking sections as safe/not is more desirable because of the switches (-ffunction-sections and -fdata-sections available already).

  - How about making the compiler to create a new section for each "safe"
atom, as it does for inline functions?

You already have a switch called -ffunction-sections and -fdata-sections to put function and data in seperate sections.

Is there any reason -ffunction-sections and -fdata-sections wouldn’t work? If it’ll work, it may be be better to say “if you want to get a better linker output use these options”, rather than defining new ELF section.

Not all users compile their code with -ffunction-sections and -fdata-sections.

This is to handle usecases when libraries use a mix of object files too.

Then how about enable these flags for -O2? I want to hear from other people cc’ed, and I may be too cautious, but I’d hesitate to define a new ELF section if there’s other mean already available to achieve the same thing.

I would probably support doing that first. A small annoyance is that
the linker requires the --gc-sections option, but most current gnu
(bfd and gold) versions support that, so we should be fine at least on
linux (and the driver already collects the distro we are in anyway in
case we need to change the default for some old distro).

Once that is in, the existing proposals for splitting sections into
atoms become speed and relocatable object size optimizations.

Cheers,
Rafael

Some numbers with -ffunction-section and -fdata-section when building clang:

no-gc:

clang is 50 152 128 bytes
clang link time is: 0m0.623s
.o files are 109 061 386 bytes

gc

clang is 49 824 592 bytes
clang link time is: 0m1.369s
.o files are 137 607 146 bytes

So there is a noticeable overhead in .o size and link time. Maybe we
should start by enabling these options at -O3?

Cheers,
Rafael

I partly agree. Implementing safe sections would be beneficial if you are getting third party libraries or system libraries(which are not usually compiled with -ffunction-sections and -fdata-sections).

It would be nice to have -ffunction-sections and -fdata-sections the default at -O2. I am not sure why it was not made the default for all these years though.

Thanks

Shankar Easwaran

I think it should also be enabled for -Os, as long as it always produces a binary equivalent or smaller than one without the flags.

For reference, with mach-o we just added a flag to the overall .o file that says all sections are "safe". The compiler always generates safe object files (unless there is inline code with non-local labels) and always sets the flag. Hand written assembly files did not have the flag by default, but savvy assembly programmers can set it.

-Nick

We could set this flag for ELF too in the ELF header, but it wouldnot not confirm to the ELF ABI.

To account safe sections, we should just create an additional section in the ELF (gcc creates a lot many sections to handle executable stack and for LTO). This would just be another section to dictate what sections are safe.

Isnt it better to have this flag set for every section in Darwin too, makes it flexible. I am not sure about the ABI concerns on Darwin though.

Thanks

Shankar Easwaran

Is there any reason -ffunction-sections and -fdata-sections wouldn't work? If it'll work, it may be be better to say "if you want to get a better linker output use these options", rather than defining new ELF section.

>From my understanding, -ffunction-sections is a good semantic match. But it introduces a lot of bloat in the .o file which the linker must process.

For reference, with mach-o we just added a flag to the overall .o file that says all sections are "safe". The compiler always generates safe object files (unless there is inline code with non-local labels) and always sets the flag. Hand written assembly files did not have the flag by default, but savvy assembly programmers can set it.

We could set this flag for ELF too in the ELF header, but it wouldnot not confirm to the ELF ABI.

To account safe sections, we should just create an additional section in the ELF (gcc creates a lot many sections to handle executable stack and for LTO). This would just be another section to dictate what sections are safe.

Or just create a new empty section with a magic name whose existence tells the linker that all sections are safe.

Isnt it better to have this flag set for every section in Darwin too, makes it flexible. I am not sure about the ABI concerns on Darwin though.

I don't see the benefit of that level of detail. Either the compiler produced the object file, so all sections are safe. Or it was hand written. If hand written, it is much easier to either say all sections are safe or none are. Listing which are safe and which are not would be a pain.

-Nick

Drive by comment here:

Other than the overhead of the section header I'm not sure what bloat
you're talking about here that the linker needs to process?

-eric

I can think of two usecases when the compiler needs to emit safe sections on a section by section basis.

* code having inline assembly (it only affects the text section)
* the compiler trying to do some optimizations that deals with data placed outside function boundaries.

Does this make sense ?

Thanks

Shankar Easwaran

The internal model of lld is "atom" based. Each atom is an indivisible run of bytes. A compiler generated function naturally matches that and should be an atom. The problem is that a hand written assembly code could look like it has a couple of functions, but there could be implicit dependencies (like falling through to next function).

If an object file has a hundred functions, that means there will be a hundred more sections (one per function). So, if we used -ffunction-sections to determine that an object file was compiler generated, we still have the problem that an assembly language programmer could have hand written extra sections that look like -ffunction-sections would have produced, but he did something tricky like have one function with two entry symbols. So, the linker would need to double check all those hundred sections.

-Nick

I’ve not been following this thread at all. However, skimming the original post, I fail to find a nice summary of what problem is trying to be solved.

By reading the rest of the thread I divine that the goal is faster links and better dead code stripping?

Making that clearer would help. Naming your sections something other than “safe” (which has very different connotations) would help more.

However, I question several fundamental assumptions:

  1. We should be very certain that -ffunction-sections is not a viable solution as it exists and is well supported in other toolchains and environments.

  2. We should talk to other ELF producers and coordinate to make sure we don’t end up creating a twisty maze of extensions here.

  3. We should step back and consider leapfrogging to a fully specialized format to reap even more performance benefits rather than messily patching ELF.

#3 may prove irrelevant if this is the only major hurdle for speeding up ELF links. My impression was otherwise.

#2 hasn’t been done by the other ELF producers, but we should strive to do better.

#1 can be solved via science.

Can you guys invent a more specific word than “safe” to describe this concept? The best thing I can come up with is something like “atomizable section”. This is basically describing code and data that the linker should feel free to strip and reorder, right? I’m not tracking this closely enough to be totally sure if that’s a reasonable word for this.

Is there any reason -ffunction-sections and -fdata-sections wouldn't work? If it'll work, it may be be better to say "if you want to get a better linker output use these options", rather than defining new ELF section.

From my understanding, -ffunction-sections is a good semantic match. But it introduces a lot of bloat in the .o file which the linker must process.

Drive by comment here:

Other than the overhead of the section header I'm not sure what bloat
you're talking about here that the linker needs to process?

The internal model of lld is "atom" based. Each atom is an indivisible run of bytes. A compiler generated function naturally matches that and should be an atom. The problem is that a hand written assembly code could look like it has a couple of functions, but there could be implicit dependencies (like falling through to next function).

I'll stipulate all of this :slight_smile:

If an object file has a hundred functions, that means there will be a hundred more sections (one per function). So, if we used -ffunction-sections to determine that an object file was compiler generated, we still have the problem that an assembly language programmer could have hand written extra sections that look like -ffunction-sections would have produced, but he did something tricky like have one function with two entry symbols. So, the linker would need to double check all those hundred sections.

I'm not talking about using -ffunction-sections to determine if
something is compiler generated, just that there's no inherent penalty
in using -ffunction-sections in general. Basically there's no benefit
(unless you allow a flag per object, etc) that says whether or not
something is "compiler generated", you may as well just use a flag to
the linker or a section in the output (the latter is a fairly common
elf-ism).

-eric

I've not been following this thread at all. However, skimming the original
post, I fail to find a nice summary of what problem is trying to be solved.

The proposal is trying to garbage collect symbols that are not referenced during the link step. In addition this proposal can be extended to keep frequently called functions/data closer to increase cache coherency.

'lld' tries to atomize all the symbols in a section, but the problem it faces on ELF is that, lld needs to tie all the atoms in a section together to respect the ELF section property. This may be relaxed if lld knows at the time of parsing the section contents, that, if you really need to tie all the atoms together in the final ELF image.

This proposal is just a way to convey information from the object file to the linker that sections in the object file can be safely converted to atoms, and they need not be tied together in whichever section they reside.

By reading the rest of the thread I divine that the goal is faster links
and better dead code stripping?

Making that clearer would help. Naming your sections something other than
"safe" (which has *very* different connotations) would help more.

"safe" is a property of a section, by which a section can be atomized and the atoms can appear anywhere in the final output file.

However, I question several fundamental assumptions:
1) We should be very certain that -ffunction-sections is not a viable
solution as it exists and is well supported in other toolchains and
environments.

-ffunction-sections and -fdata-sections would work, but that would require all third party libraries etc to make sure that they are all compiled with -ffunction-sections.

2) We should talk to other ELF producers and coordinate to make sure we
don't end up creating a twisty maze of extensions here.

This is not a problem with the general ELF community since the binutils ld/gold would not atomize sections.

3) We should step back and consider leapfrogging to a fully specialized
format to reap even more performance benefits rather than messily patching
ELF.

I dont think we should come up with another object file format.

Shankar Easwaran