Generic ABI extension proposal: address-significance tables

[Peter Collingbourne]

Hi all,

I would like to propose an extension to the generic ABI that allows for object files to specify whether each symbol is address-significant. If a symbol is address-significant, it means that the program relies on whichever section the symbol resolves to having a distinct address from other sections referred to by address-significant symbols. This means for example that a linker cannot apply identical-code folding to merge two sections which are referred to by address-significant symbols.

This also includes a proposal to codify certain behaviour of existing ELF tools so that they can safely operate on object files without breaking this or any other potential future "symbol metadata" sections.

This information allows for a more robust version of gold's "safe ICF" feature to be implemented. gold's safe ICF works by applying heuristics to symbol names and relocations. These heuristics can lead to false positives and do not work with all languages. By encoding address significance in the object file, safe ICF can be implemented using information derived from compiler analysis and/or language-specific rules, which can generally be more precise than heuristics. A C or C++ compiler would generally mark a symbol as address-significant if the symbol's address is involved in a comparison or exposed from the translation unit somehow (e.g. by returning it from a non-local function). Compilers for other languages which do not have address uniqueness guarantees can simply mark no symbols as address-significant.

The proposal is that we introduce a new section type, SHT_ADDRSIG. This section would contain a ULEB128-encoded sequence of symbol table indexes corresponding to address-significant symbols. If the section is not present in an object file, all symbols in the object file are treated as address significant. For compatibility with existing tools, the section would be marked with a flag SHF_EXCLUDE to ensure that it is dropped by linkers which do not recognize the section.

Also, the section's sh_link field would be set to the section index of the .symtab section. Similarly to relocation sections, this encodes that the section references symbol table entries by index. A tool that modifies an object file must either update the SHT_ADDRSIG section (if it is safe to do so) or set the sh_link field to 0. A linker would then be able to ignore SHT_ADDRSIG sections whose sh_link is 0.

Some existing tools that create object files (GNU objcopy, ld.bfd -r, ld.gold -r, ld.lld -r, but not llvm-objcopy at present) already set sh_link to 0 in this case for sections that they do not recognize, and I would propose that the generic ABI require this behaviour. We can do this, for example, by adding this language to the "Rules for Linking Unrecognized Sections":

If the section's sh_link field refers to the SHT_SYMTAB section, the link editor must set the sh_link field to 0.

Thanks,

Peter

[Ali Bahrami]

On 05/23/18 03:57 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Some existing tools that create object files (GNU objcopy, ld.bfd -r, ld.gold -r, ld.lld -r, but not llvm-objcopy at present) already set sh_link to 0 in this case for sections that they do not recognize, and I would propose that the generic ABI require this behaviour. We can do this, for example, by adding this language to the "Rules for Linking Unrecognized Sections":

I need to think about the rest of this a bit before commenting,
but the above immediately caught my eye. Setting sh_link to 0 for
sections you don't understand causes problems like this one,
that plagued Solaris for a couple of years until we got around to
root causing it and seeking upstream help:

https://sourceware.org/bugzilla/show_bug.cgi?id=19938

The gABI has rules that lets programs manipulate objects safely
without having to understand all their ABI-specific details. I wrote
this in the aftermath of the above bug, but they've been around since
the gABI was formed, and many utilities depend on it.

http://www.linker-aliens.org/blogs/ali/entry/how_to_strip_an_elf/

Please don't do that --- it will break a lot of things.

> A tool that modifies an object file must either update the SHT_ADDRSIG
> section (if it is safe to do so) or set the sh_link field to 0. A
> linker would then be able to ignore SHT_ADDRSIG sections whose
> sh_link is 0.

Even if the objection above wasn't a factor, I don't really follow how
an sh_link of 0 can be interpreted as meaning that the linker is
free to ignore the section. There's a circular problem here --- since
the section isn't understood, the meaning of its sh_link is also
not understood. If something like this ends up in the gABI, all the
gABI conforming ELF platforms will have to learn about the section.

- Ali

[Peter Collingbourne]

On Wed, May 23, 2018 at 3:40 PM Ali Bahrami <Ali.B...@oracle.com> wrote:

On 05/23/18 03:57 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Some existing tools that create object files (GNU objcopy, ld.bfd -r, ld.gold -r, ld.lld -r, but not llvm-objcopy at present) already set sh_link to 0 in this case for sections that they do not recognize, and I would propose that the generic ABI require this behaviour. We can do this, for example, by adding this language to the "Rules for Linking Unrecognized Sections":

    I need to think about the rest of this a bit before commenting,
but the above immediately caught my eye. Setting sh_link to 0 for
sections you don't understand causes problems like this one,
that plagued Solaris for a couple of years until we got around to
root causing it and seeking upstream help:

     https://sourceware.org/bugzilla/show_bug.cgi?id=19938

The gABI has rules that lets programs manipulate objects safely
without having to understand all their ABI-specific details. I wrote
this in the aftermath of the above bug, but they've been around since
the gABI was formed, and many utilities depend on it.

     http://www.linker-aliens.org/blogs/ali/entry/how_to_strip_an_elf/

Please don't do that --- it will break a lot of things.

Note that the rule would not reset sh_link on every unrecognized section, just the ones that link to the SHT_SYMTAB section. This seems reasonable to me: when a tool such as objcopy or ld -r operates on an object file, it is removing the symtab section and replacing it with a symtab of its own, so there is no longer a section to link to. A tool would still be required to map the sh_link on any other unrecognized sections.

It looks like you have the following mapping in Solaris:

.SUNW_dynsymsort links to .SUNW_ldynsym

.SUNW_ldynsym links to ??? (maybe a string table?)

The proposed rule would not break the sh_link for either of those, as long as they do not link to SHT_SYMTAB. Note also that the rule is simply documenting what objcopy and other tools are already doing, so if that breaks something, we would probably have found out about it by now.

 > A tool that modifies an object file must either update the SHT_ADDRSIG
 > section (if it is safe to do so) or set the sh_link field to 0. A
 > linker would then be able to ignore SHT_ADDRSIG sections whose
 > sh_link is 0.

Even if the objection above wasn't a factor, I don't really follow how
an sh_link of 0 can be interpreted as meaning that the linker is
free to ignore the section. There's a circular problem here --- since
the section isn't understood, the meaning of its sh_link is also
not understood. If something like this ends up in the gABI, all the
gABI conforming ELF platforms will have to learn about the section.

Sorry, when I said "linker" above I was referring to a linker that understands SHT_ADDRSIG. A linker that does not understand the section will ignore it naturally via the SHF_EXCLUDE flag.

Peter

- Ali

--
You received this message because you are subscribed to the Google Groups "Generic System V Application Binary Interface" group.
To unsubscribe from this group and stop receiving emails from it, send an email to generic-abi...@googlegroups.com.
To post to this group, send email to gener...@googlegroups.com.
Visit this group at https://groups.google.com/group/generic-abi.
For more options, visit https://groups.google.com/d/optout.

[Ali Bahrami]

On 05/23/18 05:07 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> The proposed rule would not break the sh_link for either of those, as long as they do not link to SHT_SYMTAB.

But why shouldn't they link to SHT_SYMTAB? That's a very big restriction.
Symbol tables are the most common targets of sh_link. The odds are better than
not that any new section type wants to reference a symbol table. We don't
want to preclude that.

> Sorry, when I said "linker" above I was referring to a linker that
> understands SHT_ADDRSIG.

OK, that helps. I guess that you are concerned about the
following scenario:

- You put a new gold in the world that understands this
feature.

- You get the compilers to use it.

- You can't ensure that the binutils or other packages on some
systems that see the results of these new features will be
SHT_ADDRSIG aware, so you might encounter objects that have
been corrupted by objcopy (to pick one possibility). You
don't want to error out in this case.

That's a real problem, but it's a temporary one, because the rest of the
tools will catch up fairly quickly. And while ignoring SHT_ADDRSIG in this
case might be fine, that might not be true for other new sections. I would
prefer to solve this without permanently complicating the gABI.

I'll suggest that this could be solved by having gold ignore SHT_ADDRSIG
sections with sh_link set to 0, for a respectful period of time (a year
or 2, or whatever), until the rest of the toolchain catches up, and then
later removing that implementation loophole from the code. There's no
reason to have the gABI require that --- it's just a temporary implementation
detail used to bootstrap a new feature.

- Ali

[Ali Bahrami]

On 05/23/18 03:57 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> I would like to propose an extension to the generic ABI that allows for object files to specify whether each symbol is address-significant. If a symbol is address-significant, it means that the program relies on whichever section the symbol resolves to having a distinct address from other sections referred to by address-significant symbols. This means for example that a linker cannot apply identical-code folding to merge two sections which are referred to by address-significant symbols.

As I said, I want to sleep on this a bit before getting into a
detailed discussion. However, I have a question to ask that would
help me in understanding what you're going for.

Would it work for you if we reversed the sense of this feature, so
that the default is not to merge untagged things, and then to tag
those that can be merged?

-----

I think that you're saying that gold has an optimization that
eliminates duplicate copies of code, by throwing out the duplicates
and having all those symbols reference the one remaining instance.
Gold has heuristics for knowing when this is safe, but sometimes
it's wrong and merges things that need to have unique addresses.
(I'll guess: Code that compares addresses to decide if 2 function
pointers reference the same thing needs those functions to be
"address significant"). It would be better if the compiler
labeled this stuff, and link-editors didn't guess about it.

I ask, because your feature sounds a lot like the existing SHF_MERGE
section flag, when combined with SHF_STRINGS, except that it has the
opposite sense (merging has to be requested rather than disabled). As
such, my first reaction to your proposal was to wonder why that existing
SHF_MERGE mechanism couldn't be used to handle this. Mergable functions
could be put in a .text section with SHF_MERGE|SHF_EXECINSTR, to identify
things that can be combined, and address-significant things would go into
a normal .text section that does not have these flags set. Naive
link-editors would not be affected by that, and would produce valid
results, just a bit larger than otherwise. New link-editors would
have the option of merging.

That's not a counter proposal yet --- I don't think I understand
what you're getting at well enough to know if it's a good idea, but
I mention it so that you'll understand why I asked the question above.

- Ali

[Peter Collingbourne]

On Wed, May 23, 2018 at 6:28 PM Ali Bahrami <Ali.B...@oracle.com> wrote:

On 05/23/18 03:57 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> I would like to propose an extension to the generic ABI that allows for object files to specify whether each symbol is address-significant. If a symbol is address-significant, it means that the program relies on whichever section the symbol resolves to having a distinct address from other sections referred to by address-significant symbols. This means for example that a linker cannot apply identical-code folding to merge two sections which are referred to by address-significant symbols.


    As I said, I want to sleep on this a bit before getting into a
detailed discussion. However, I have a question to ask that would
help me in understanding what you're going for.

Would it work for you if we reversed the sense of this feature, so
that the default is not to merge untagged things, and then to tag
those that can be merged?

-----

I think that you're saying that gold has an optimization that
eliminates duplicate copies of code, by throwing out the duplicates
and having all those symbols reference the one remaining instance.
Gold has heuristics for knowing when this is safe, but sometimes
it's wrong and merges things that need to have unique addresses.
(I'll guess: Code that compares addresses to decide if 2 function
pointers reference the same thing needs those functions to be
"address significant"). It would be better if the compiler
labeled this stuff, and link-editors didn't guess about it.

Yes, all of that is correct.

I ask, because your feature sounds a lot like the existing SHF_MERGE
section flag, when combined with SHF_STRINGS, except that it has the
opposite sense (merging has to be requested rather than disabled). As
such, my first reaction to your proposal was to wonder why that existing
SHF_MERGE mechanism couldn't be used to handle this. Mergable functions
could be put in a .text section with SHF_MERGE|SHF_EXECINSTR, to identify
things that can be combined, and address-significant things would go into
a normal .text section that does not have these flags set. Naive
link-editors would not be affected by that, and would produce valid
results, just a bit larger than otherwise. New link-editors would
have the option of merging.

That's not a counter proposal yet --- I don't think I understand
what you're getting at well enough to know if it's a good idea, but
I mention it so that you'll understand why I asked the question above.

Unfortunately, this would not work because the attribute has to be on the symbol and not the section. Consider two translation units:

1.c:

void f() {}

2.c:

void f();

bool g(void (*p)()) {

  return p == f;

}

In this case it is 2.c which is causing f to become address-significant, so 2.o has to contain something that makes f address-significant. The most natural place for that information to live would be something associated with the symbol f in 2.o.

[Ali Bahrami]

You asked some Solaris specific questions that I didn't
address in the previous message, since my overall point isn't
about what Solaris (or anyone else) does today, it's about keeping
options open for the future.

On 05/23/18 05:07 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Note that the rule would not reset sh_link on every unrecognized section, just the ones that link to the SHT_SYMTAB section. This seems reasonable to me: when a tool such as objcopy or ld -r operates on an object file, it is removing the symtab section and replacing it with a symtab of its own, so there is no longer a section to link to. A tool would still be required to map the sh_link on any other unrecognized sections.

It really depends --- I guess I would expect these sections to
be updated so that they point at the new symbol table created by
objcopy, rather than being disabled.

My big takeaway there however is that tools like objcopy need
to know about the sections involved --- other than the sh_link/sh_info
rules I discussed in that blog, it's really not safe to simply disable
sections without an understanding of what they mean.

objcopy did that, and it broke my objects, and having the gABI modified
to say that it's OK really doesn't help. :-)

>
> It looks like you have the following mapping in Solaris:
>
> .SUNW_dynsymsort links to .SUNW_ldynsym
> .SUNW_ldynsym links to ??? (maybe a string table?)

We document the sh_link/sh_info rules for our ABI in our
Linker and Libraries Guide. See Table 20 here:

https://docs.oracle.com/cd/E37838_01/html/E36783/man-s.html#scrolltoc

- Ali

[Peter Collingbourne]

On Wed, May 23, 2018 at 6:07 PM Ali Bahrami <Ali.B...@oracle.com> wrote:

On 05/23/18 05:07 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> The proposed rule would not break the sh_link for either of those, as long as they do not link to SHT_SYMTAB.

    But why shouldn't they link to SHT_SYMTAB? That's a very big restriction.
Symbol tables are the most common targets of sh_link. The odds are better than
not that any new section type wants to reference a symbol table. We don't
want to preclude that.

Note that it would not be precluded. With both the status quo and the new rule, creating a new symtab-linked section would mean changing tools that update symbol tables to also recognize and update the new section, because a sh_link to symtab generally means that the section contains or otherwise depends on symbol table indexes and therefore would need to be updated with the symbol table (see: SHT_REL, SHT_SYMTAB_SHNDX). Since the section is recognized it means that sh_link for such sections would continue to point to symtab. All that the rule would allow is for a gABI-compliant tool that does not recognize the associated section to modify the symbol table and for said modification to be detected by downstream tools that do recognize the section. Such tools can handle the modification in two ways:

- if the associated section is required, they can error out with a request to update tools.

- if the associated section is optional, they can ignore the section.

One other thing that this rule would allow for is optional platform-ABI-specific sections that contain symbol table indexes (I'm thinking about things like compiler- or target-specific symbol optimization hints). With the status quo, a gABI-compliant tool would be allowed to change symbol table indexes and therefore corrupt the object file, and because the section is platform-specific the gABI would never specify anything about it that would allow the modification to be detected.

> Sorry, when I said "linker" above I was referring to a linker that
> understands SHT_ADDRSIG.

OK, that helps. I guess that you are concerned about the
following scenario:

     - You put a new gold in the world that understands this
       feature.

     - You get the compilers to use it.

     - You can't ensure that the binutils or other packages on some
       systems that see the results of these new features will be
       SHT_ADDRSIG aware, so you might encounter objects that have
       been corrupted by objcopy (to pick one possibility). You
       don't want to error out in this case.

Correct, nor do I want miscompiles as a result of objcopy changing symbol indexes by moving symbols around.

That's a real problem, but it's a temporary one, because the rest of the
tools will catch up fairly quickly. And while ignoring SHT_ADDRSIG in this
case might be fine, that might not be true for other new sections. I would
prefer to solve this without permanently complicating the gABI.

I'll suggest that this could be solved by having gold ignore SHT_ADDRSIG
sections with sh_link set to 0, for a respectful period of time (a year
or 2, or whatever), until the rest of the toolchain catches up, and then
later removing that implementation loophole from the code. There's no
reason to have the gABI require that --- it's just a temporary implementation
detail used to bootstrap a new feature.

That *might* work for this specific section, but the transition period could be much longer than a year or two (one feature that springs to mind is .gnu.linkonce, which was superseded by COMDAT in the early 2000's but is still supported by the GNU linkers and somewhat by lld, in part because glibc still uses it on i386). On the other hand, there also seem to be good reasons to adopt the rule that I've proposed.

[Ali Bahrami]

On 05/23/18 07:37 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Unfortunately, this would not work because the attribute has to be on the symbol and not the section. Consider two translation units:
>
> 1.c:
>
> void f() {}
>
> 2.c:
>
> void f();
> bool g(void (*p)()) {
>   return p == f;
> }
>
> In this case it is 2.c which is causing f to become address-significant, so 2.o has to contain something that makes f address-significant. The most natural place for that information to live would be something associated with the symbol f in 2.o.

I see... address significance is an attribute of the reference,
not of the definition. The compiler sees a use of f() that requires
a unique address, and it tags the symbol with that attribute.

Suppose the function took 2 arguments, rather than hardwiring f():

bool g(void (*p1)(), void (*p2)()) {
return p1 == p2;
}

Now, suppose that this function g() exists in a shared object
that is dynamically loaded at runtime by this main program:


extern bool g(void (*p1)(), void (*p2)());
void f1() {}
void f2() {}

main()
{
printf("f1 and f2 are different: %s\n",
g(f1, f2) ? "yes" : "no");
}

f1() and f2() are address significant, but the compiler can't tell.
I guess that the call to g() taints both f1 and f2 as address-significant
based on not being able to rule it out?

If I'm understanding the above, a symbol is only address-insignificant
when:

- Its address isn't taken

- It does not emerge from the link-edit as a global symbol.

I could make it even harder on the compiler, by moving f1() and f2()
into yet another separately linked shared object. But then, I guess the
compiler would still decide that f1() and f2() are address significant,
based on the fact that they are exported as global symbols from a shared
object?

At least on Solaris, this last case is particularly opaque, because
it's the address of the PLT getting compared. f1() and f2() would not
compare as equal even if they really are one function body in their
shared object, because they'd each have a different PLT in the main
program, and therefore, g() would be passed 2 different addresses.
The rule about not emerging as a global symbol might not be necessary.

Tricky stuff...

- Ali

[Peter Collingbourne]

Thanks for the link. I see that the sh_link fields for some Solaris-specific sections are specified as pointing to "The section header index of the associated symbol table.". According to the documentation for one of those sections, it can appear in an ET_REL and can contain symbol indexes:

https://docs.oracle.com/cd/E37838_01/html/E36783/chapter7-28.html#scrolltoc

Does that mean that I cannot write a strip tool that can handle Solaris object files without understanding those sections?

[Peter Collingbourne]

Yes. Essentially, if a pointer leaks out of the translation unit in any way, the compiler must mark the symbol as address-significant. 

If I'm understanding the above, a symbol is only address-insignificant
when:

     - Its address isn't taken

Note that it's fine to take an address, it just cannot leak outside the translation unit. So for example, in this translation unit:

void f1();

void f2();

void f(bool b) {

  void (*p)();

  p = b ? f1 : f2;

  p();

}

or even in this one:

void f1();

void f2();

typedef void (*fp)();

static fp p(bool b) {

  return b ? f1 : f2;

}

void f(bool b) {

  p(b)();

}

it would be fine for f1 and f2 not to appear in the address-significance table.

     - It does not emerge from the link-edit as a global symbol.

I could make it even harder on the compiler, by moving f1() and f2()
into yet another separately linked shared object. But then, I guess the
compiler would still decide that f1() and f2() are address significant,
based on the fact that they are exported as global symbols from a shared
object?

Exactly. The rules that I have implemented in my prototype are that a symbol is address-significant if it:

- appears in the output file's SHT_DYNSYM, or

- appears in an SHT_ADDRSIG section in any object file.

At least on Solaris, this last case is particularly opaque, because
it's the address of the PLT getting compared. f1() and f2() would not
compare as equal even if they really are one function body in their
shared object, because they'd each have a different PLT in the main
program, and therefore, g() would be passed 2 different addresses.
The rule about not emerging as a global symbol might not be necessary.

But the caller of g (from your example) could appear in a shared object as well, no? In that case, the canonical addresses of f1 and f2 may come from their definitions in the shared object, I'd imagine. So there'd still need to be a rule about refusing to merge anything in SHT_DYNSYM.

Peter

Tricky stuff...

[Ali Bahrami]

On 05/23/18 09:37 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Thanks for the link. I see that the sh_link fields for some Solaris-specific sections are specified as pointing to "The section header index of the associated symbol table.". According to the documentation for one of those sections, it can appear in an ET_REL and can contain symbol indexes:
> https://docs.oracle.com/cd/E37838_01/html/E36783/chapter7-28.html#scrolltoc
>
> Does that mean that I cannot write a strip tool that can handle Solaris object files without understanding those sections?

You can: Strip only needs to understand is that those sections
are related to each other through sh_link/sh_info. It can safely
remove all the sections in such a group, without interpreting the
section content, so understanding is not required.

Altering content is different. Rewriting the symtab and disconnecting
the sections that are not understood is dubious,

- Ali

[Peter Collingbourne]

I'm not talking about stripping the symbols from an object file, but stripping just the debug info. Doing that involves removing debug info sections, which might involve removing section symbols for those sections from the symbol table. How can I do that if I cannot rewrite the linked sections?

[Ali Bahrami]

On 05/24/18 10:26, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> I'm not talking about stripping the symbols from an object file, but stripping just the debug info. Doing that involves removing debug info sections, which might involve removing section symbols for those sections from the symbol table. How can I do that if I cannot rewrite the linked sections?

That's a good question, and not one that I'm sure is
really written down anywhere.

You can do this by putting some sort of filler content
for that symbol in the symbol table, so that all other
symbols retain their current index. If you don't move
things around, you don't have to update anything that
references them.

Solaris appears to zero sh_name for that section symbol. Let's
look at a hello world example, focusing on .debug_line:

% elfdump -cN.debug_line a.out

Section Header[33]: sh_name: .debug_line
sh_addr: 0 sh_flags: 0
sh_size: 0xd4 sh_type: [ SHT_PROGBITS ]
sh_offset: 0x21c4 sh_entsize: 0
sh_link: 0 sh_info: 0
sh_addralign: 0x1
% elfdump -sN.symtab a.out | grep debug_line
[34] 0 0 SECT LOCL D 0 .debug_line

Remove that section, and see that the section is gone:

% mcs -d -n .debug_line a.out
% elfdump -cN.debug_line a.out
% elfdump -sN.symtab a.out | grep debug_line

What happened to the symbol table? I won't show it here, but
its size remained the same, and everything else stayed in place.
However, symbol [34] has been rewritten:

% elfdump -sN.symtab a.out | grep '\[34\]'
[34] 0 0 SECT LOCL D 0 .interp

It just so happens that ".interp" is the first string in the
.shstrtab for that object. That's pretty ugly, and I won't
defend it beyond noting that it's been that way since it was
born in New Jersey in the 80's, and I guess it hasn't caused
any problems. I think we could probably do better here, if only
by pointing it at a name like "deleted-section", but given that
no one has noticed in decades, perhaps it's OK.

- Ali

[Peter Collingbourne]

Leaving filler content in place for section symbols of deleted sections seems reasonable. I guess the important thing that a strip tool needs to do is replace not the symbol's st_name but the st_shndx. My reading of the output you provided, combined with the documentation for elfdump:

https://docs.oracle.com/cd/E26502_01/html/E26507/glmqw.html

is that .interp is in the "shndx" column not the "name" column, so maybe the Solaris strip tool is setting the st_shndx to 1? As you mention, since that's been the case since the 80s, it's probably fine. I guess a more technically correct value for st_shndx in this case would be SHN_UNDEF, which might help if a platform adds a new linked section and the consumer of the section needs to detect the case where the associated section for a section symbol has been stripped.

My takeaway is: it is possible to write a gABI-compliant strip tool in the way that you mention in your blog post (GNU strip, eu-strip and llvm-strip evidently aren't, since they all change symbol indexes as a result of actually removing debug section symbols). Such a tool can validly preserve the sh_link on any linked sections, and any downstream tools need to be able to handle the filler content somehow. But if a tool does change symbol indexes or does anything else to the symbol table other than replacing symbol table entries for removed sections with filler content it must have platform ABI-specific knowledge to update the linked sections. That means that if a tool is asked to do something like that it probably needs to refuse to operate on an object file with an unrecognized linked section, or at least print a warning.

So for addrsig, in terms of short-term solutions, the idea of using sh_link=0 as a signal that a non-gABI-compliant strip tool (or an old platform-specific tool) has operated on the object file may be sufficient for now. There was also a suggestion of hashing the contents of .symtab and .strtab, storing that in the addrsig section's sh_info field and having the linker ignore any addrsig section with a non-matching hash, which may be better since it doesn't depend on any specific tool behaviour.

It still might be nice to do something in the gABI for optional platform-specific linked sections, though. If I add support for such a new section to my compiler and my linker, I shouldn't need to update everyone else's tools at the same time to recognize my new section (I'm thinking of platforms like Linux with many tool vendors: GCC, LLVM, ICC, etc.). So here's a proposal: we can add a flag to the section header (akin to SHF_INFO_LINK) that tells a tool that it should discard the section if the linked section is updated.

[Peter Collingbourne]

Last night I realised that there is a possible other use case for SHF_MERGE on sections: we can use it in the case where the compiler has language-specific knowledge that the address of the section will never be address-significant. Two good examples of this in C++ are vtables and virtual functions: a program cannot directly take the address of either, but they can frequently be targets of identical code folding. The main utility of this is that we can merge these sections even if they are referenced by the SHT_DYNSYM, which wouldn't be possible with just the SHT_ADDRSIG information.

[Ali Bahrami]

On 05/23/18 15:57, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> The proposal is that we introduce a new section type, SHT_ADDRSIG. This section would contain a ULEB128-encoded sequence of symbol table indexes corresponding to address-significant symbols. If the section is not present in an object file, all symbols in the object file are treated as address significant. For compatibility with existing tools, the section would be marked with a flag SHF_EXCLUDE to ensure that it is dropped by linkers which do not recognize the section.
>
> Also, the section's sh_link field would be set to the section index of the .symtab section. Similarly to relocation sections, this encodes that the section references symbol table entries by index. A tool that modifies an object file must either update the SHT_ADDRSIG section (if it is safe to do so) or set the sh_link field to 0. A linker would then be able to ignore SHT_ADDRSIG sections whose sh_link is 0.

I've had a chance to think about this, and to discuss it with
my partner in ELF crime, Rod Evans. We're generally supportive
of the idea of giving compilers a way to tag reference symbols to
say that they must point at a unique address. We have some thoughts
about the specifics, while I'll list below. Think of this as more
grist for the mill.

I'm going to ignore the sh_link/sh_info discussion here, and
will close the loop on that separately.

-----

Excluding the part about sh_link of 0, having the sh_link for this
section point at the symbol table it corresponds to is clearly the
right thing.

-----

I'm puzzled about the SHF_EXCLUDE idea. Yes, it will let old
linkers ignore the section, but it also requires new linkers
to ignore it. Are you proposing that new linkers will recognize
an SHT_ADDRSIG, and ignore an SHF_EXCLUDE? That seems problematic.

-----

There's a hard naming problem here: I'd be happy to see a shorter
more specific term than "address significance", but I don't really
have a good suggestion at the moment, so let's go with it for now.

-----

The ULEB128 encoding is different than how other ELF sections have
been defined (noting that uleb128 is used by dwarf, but that dwarf
sections are not core ELF). Specifically, I would have expected an
array of words, which libelf can understand and xlate as part of
loading an object. I'd prefer not to introduce the use of ULEB128
for core ELF sections.

I'm going to guess that you're proposing ULEB128 because it is compact.
Have you considered using section compression instead? We've got that
in the gABI now, and I think the GNU implementation has been in the
field long enough now that you should assume its available:

https://gnu.wildebeest.org/blog/mjw/2016/01/13/elf-libelf-compressed-sections-and-elfutils/

http://www.linker-aliens.org/blogs/ali/entry/elf_section_compression/

-----

It's convenient if sections that augment symbol tables are structured
as an array with the same number of elements as the symbol table they
belong to. That way, all the data for any given symbol can be accessed
by indexing the appropriate array with the symbol index. One example
of this is SHT_SYMTAB_SHNDX. Forgive all the Solaris examples (it's
what I know best), but we have several others:

.SUNW_capinfo: Per symbol capabilities info
.SUNW_syminfo: Symbol flags, and direct bindings
.SUNW_versym : ELF versioning index (GNU has this also,
see SHT_GNU_versym)

Those Solaris sections are described here:

https://docs.oracle.com/cd/E37838_01/html/E36783/glcfv.html#scrolltoc

I mention all of this, because generally speaking, one thing we've
needed more than once, is a way to add a flag to an ELF symbol. And
what you're proposing with ADDRSIG is really just another example.
It's always tempting to shoehorn things like this into the symbol
st_info/st_other fields, but that never works well, because those
things (binding, visibility, etc) are somewhat orthogonal.

In the Solaris ABI, we solved this as part of the .SUNW_syminfo
(SHT_SUNW_syminfo), and if this was a Solaris only feature, I would
implement it by defining SYMINFO_FLG_ADDRSIG in .SUNW_syminfo for this.

Pulling all of those threads together, I think that defining an
SHT_SYMATTR section, defined as an array of words containing flag
bits to augment symbols, would be very useful for the gABI, as well
as offering a solution to your immediate problem. Such a flag array
would be associated to its symbol table with sh_link, and the first
flag defined would be:

#define SYMATTR_FLG_ADDRSIG

I know that's going to be a sparse array, which you might see as
wasted space, but for cases where that's a problem, section compression
can make quick work of it, and a flags section would set the gABI up to
handle other similar issues without having to define even more sections.

-----

To summarize:

- Generally for doing something in this ADDRSIG area

- Not in love with the ULEB128 idea

- The idea of an array of symbol indexes is OK, but we'd
like you to consider the flags section idea --- it's
useful beyond just the problem you're trying to solve.

I'd like to hear some other voices --- any of this is a fairly
large change, and general agreement is needed. It's clearly a bit
early to standardize, but I think you're on a track that will
get you there.

Thanks for the opportunity to comment.

- Ali

[Peter Collingbourne]

On Thu, May 24, 2018 at 4:50 PM Ali Bahrami <Ali.B...@oracle.com> wrote:

On 05/23/18 15:57, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> The proposal is that we introduce a new section type, SHT_ADDRSIG. This section would contain a ULEB128-encoded sequence of symbol table indexes corresponding to address-significant symbols. If the section is not present in an object file, all symbols in the object file are treated as address significant. For compatibility with existing tools, the section would be marked with a flag SHF_EXCLUDE to ensure that it is dropped by linkers which do not recognize the section.
>
> Also, the section's sh_link field would be set to the section index of the .symtab section. Similarly to relocation sections, this encodes that the section references symbol table entries by index. A tool that modifies an object file must either update the SHT_ADDRSIG section (if it is safe to do so) or set the sh_link field to 0. A linker would then be able to ignore SHT_ADDRSIG sections whose sh_link is 0.


    I've had a chance to think about this, and to discuss it with
my partner in ELF crime, Rod Evans. We're generally supportive
of the idea of giving compilers a way to tag reference symbols to
say that they must point at a unique address. We have some thoughts
about the specifics, while I'll list below. Think of this as more
grist for the mill.

I'm going to ignore the sh_link/sh_info discussion here, and
will close the loop on that separately.

-----

Excluding the part about sh_link of 0, having the sh_link for this
section point at the symbol table it corresponds to is clearly the
right thing.

-----

I'm puzzled about the SHF_EXCLUDE idea. Yes, it will let old
linkers ignore the section, but it also requires new linkers
to ignore it. Are you proposing that new linkers will recognize
an SHT_ADDRSIG, and ignore an SHF_EXCLUDE? That seems problematic.

Interestingly, I can't seem to find the SHF_EXCLUDE flag described in the gABI. The Solaris documentation describes it as:

"This section is excluded from input to the link-edit of an executable or shared object. This flag is ignored if the SHF_ALLOC flag is also set, or if relocations exist against the section."

That certainly supports your interpretation.

But a comment in a GNU binutils header file describes it as:

"Link editor is to exclude this section from executable and shared library that it builds when those objects are not to be further relocated."

That is what I've always understood SHF_EXCLUDE to mean, and it wouldn't require new linkers to ignore the section.

To be honest, the question of when the SHF_EXCLUDE sections are dropped inside the linker seems rather academic, as I don't think it should normally affect the observable behaviour. It only really seems to matter in cases like this where a section's contents are expected to be interpreted specially by linkers that understand it. In that case, I don't really see the utility in an interpretation that requires the linker to ignore such sections.

I'd probably advocate for the gABI to define SHF_EXCLUDE using the GNU interpretation. In any event, I imagine that the SHF_EXCLUDE can be seen as a GNU-gABI specific compatibility hack.

The idea of a general flags section mapped onto the symtab section is something that may be worth considering. It's one idea that I had as well, but I ended up not proposing it because I expected the array to be sparse and was indeed concerned about object file size bloat: I want clang to emit this section by default, and I have internal customers who care a lot about object file size. I hadn't considered compressing it, though.

With my current prototype I measured the object file size increase when building clang at 0.08%, and 0.1% is a nice target to shoot for for something that's enabled by default. However, it may be worth taking a slightly larger hit to make it cheaper to add new flags in the future. I will do some measurements and get back to the list.

Peter

-----

To summarize:

     - Generally for doing something in this ADDRSIG area

     - Not in love with the ULEB128 idea

     - The idea of an array of symbol indexes is OK, but we'd
       like you to consider the flags section idea --- it's
       useful beyond just the problem you're trying to solve.

I'd like to hear some other voices --- any of this is a fairly
large change, and general agreement is needed. It's clearly a bit
early to standardize, but I think you're on a track that will
get you there.

Thanks for the opportunity to comment.

- Ali

[Ali Bahrami]

Coming back around on the sh_link/sh_info aspect of this
discussion...

On 05/23/18 08:53 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> That *might* work for this specific section, but the transition period could be much longer than a year or two (one feature that springs to mind is .gnu.linkonce, which was superseded by COMDAT in the early 2000's but is still supported by the GNU linkers and somewhat by lld, in part because glibc still uses it on i386). On the other hand, there also seem to be good reasons to adopt the rule that I've proposed.

That really only says that transitions can take a long time,
unless something or someone is able to apply some back pressure
on the issue to flush things out.

The problem with gnu.linkonce as an example is that COMDAT hasn't fully
superseded it. My understanding is that the dwarf sections are not
COMDATified, which means that even when comdat is used, there's
some linkonce handling required. That was discussed here in April:

https://groups.google.com/forum/#!topic/generic-abi/A-1rbP8hFCA

I hold out hope that linkonce will die a richly deserved death, as I
did (literally) a decade ago, but even now, it's not going to be soon.

> Leaving filler content in place for section symbols of deleted sections seems reasonable. I guess the important
> thing that a strip tool needs to do is replace not the symbol's st_name but the st_shndx. My reading of the
> output you provided, combined with the documentation for elfdump:
> https://docs.oracle.com/cd/E26502_01/html/E26507/glmqw.html
> is that .interp is in the "shndx" column not the "name" column, so maybe the Solaris strip tool is setting
> the st_shndx to 1? As you mention, since that's been the case since the 80s, it's probably fine.
> I guess a more technically correct value for st_shndx in this case would be SHN_UNDEF, which might
> help if a platform adds a new linked section and the consumer of the section needs to detect the
> case where the associated section for a section symbol has been stripped.

You're right, that's what's happening. I forgot that we're looking at
STT_SECTION symbols. These often have a 0 st_name, and the name of the
section they reference is used as the symbol name. It's st_shndx == 1.
Hence, the stubbed out symbol table entry becomes a harmless duplicate:

% elfdump -sN.symtab a.out | grep .interp | grep SECT
[2] 0x400190 0 SECT LOCL D 0 .interp

[34] 0 0 SECT LOCL D 0 .interp

I apologize to the nameless Bell Labs guy from the 80's that I
slandered earlier. :-)

> My takeaway is: it is possible to write a gABI-compliant strip tool in the way
> that you mention in your blog post (GNU strip, eu-strip and llvm-strip evidently
> aren't, since they all change symbol indexes as a result of actually removing
> debug section symbols). Such a tool can validly preserve the sh_link on any
> linked sections, and any downstream tools need to be able to handle the filler
> content somehow. But if a tool does change symbol indexes or does anything else
> to the symbol table other than replacing symbol table entries for removed
> sections with filler content it must have platform ABI-specific knowledge to
> update the linked sections. That means that if a tool is asked to do something
> like that it probably needs to refuse to operate on an object file with an
> unrecognized linked section, or at least print a warning.

Yes, that's what I think also.

> So for addrsig, in terms of short-term solutions, the idea of using sh_link=0
> as a signal that a non-gABI-compliant strip tool (or an old platform-specific
> tool) has operated on the object file may be sufficient for now. There was
> also a suggestion of hashing the contents of .symtab and .strtab, storing
> that in the addrsig section's sh_info field and having the linker ignore
> any addrsig section with a non-matching hash, which may be better since
> it doesn't depend on any specific tool behaviour.

I'm in favor of solving this without dragging the gABI into it, and this
largely sounds good. Not so sure about the sh_info idea though --- setting
the sh_link to 0 seems sufficient, and a non-zero sh_info will raise
other questions.

> It still might be nice to do something in the gABI for optional
> platform-specific linked sections, though. If I add support for
> such a new section to my compiler and my linker, I shouldn't need
> to update everyone else's tools at the same time to recognize my

> new section(I'm thinking of platforms like Linux with many tool

> vendors: GCC, LLVM, ICC, etc.). So here's a proposal: we can add
> a flag to the section header (akin to SHF_INFO_LINK) that tells
> a tool that it should discard the section if the linked section
> is updated.

If we have to solve this in the gABI, then this is a much better way
to do it. I'll suggest thinking more generally: Call the flag SHF_OPTIONAL
with a definition that says something like:

SHF_OPTIONAL
A section with the SHF_OPTIONAL flag can be safely ignored
or removed by link-editors and other tools. The result of a
link-edit that omits processing such a section will be a
valid object that operates normally, but it may lack the
benefit of an optimization that would have otherwise been
provided. SHF_OPTIONAL is only allowed for sections that do
not set SHF_ALLOC.

The main generalization being that a tool can drop this section for any
reason, or none whatsoever. It need not be because a linked section is
being updated, though that's a good reason to do it.

If SHF_OPTIONAL is not set, a tool either needs to understand the ABI
and have the ability to rewrite it, or it must throw an error and quit.
If SHF_OPTIONAL is set, then there's a third option --- strip the section
from the output, and ignore it. Note that honoring SHF_OPTIONAL itself
is also optional. A tool might still throw an error and quit, and that
would be legit.

Also note that zeroing sh_link isn't a choice: You don't leave damaged
bits behind, one way or another. It's either strip, fix, or fail.

I'm not really sure how much we need this though --- I sure hope we're not
going to be adding *too* many new sections that reference symbol tables.
This ought to be a fairly rare thing, and maybe something that can just
be handled case by case.

- Ali

[Ali Bahrami]

On 05/24/18 07:26 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Interestingly, I can't seem to find the SHF_EXCLUDE flag described in the gABI. The Solaris documentation describes it as:
> "This section is excluded from input to the link-edit of an executable or shared object. This flag is ignored if the SHF_ALLOC flag is also set, or if relocations exist against the section."
> That certainly supports your interpretation.
>
> But a comment in a GNU binutils header file describes it as:
> "Link editor is to exclude this section from executable and shared library that it builds when those objects are not to be further relocated."
> That is what I've always understood SHF_EXCLUDE to mean, and it wouldn't require new linkers to ignore the section.
>
> To be honest, the question of when the SHF_EXCLUDE sections are dropped inside the linker seems rather academic, as I don't think it should normally affect the observable behaviour. It only really seems to matter in cases like this where a section's contents are expected to be interpreted specially by linkers that understand it. In that case, I don't really see the utility in an interpretation that requires the linker to ignore such sections.
>
> I'd probably advocate for the gABI to define SHF_EXCLUDE using the GNU interpretation. In any event, I imagine that the SHF_EXCLUDE can be seen as a GNU-gABI specific compatibility hack.

Our records show that SHF_EXCLUDE was added by Sun in 1996 as

PSARC/1996/249: Addition of SHF_EXCLUDE Section Attribute Flag

This was added for the PowerPC port of Solaris (yes, there was one,
but it didn't last long), and then extended to the other platforms.
You'll notice that it's in the ELF platform range numerically. From
the Solaris <sys/link.h>:

#define SHF_MASKPROC 0xf0000000 /* processor specific values */
/*
* The following processor specific flags have gained wide acceptance, and are
* implemented across all Solaris platforms.
*/
#define SHF_ORDERED 0x40000000 /* (EOL) See SHF_LINK_ORDER */
#define SHF_EXCLUDE 0x80000000

The description in the PSARC case is identical to that in the
Solaris Linkers and Libraries guide today.

I don't know why it's not in the gABI, or how it ended up in the
GNU tools, but our headers and documentation must have been
involved. That's water under the bridge now, by 22 years,
and whatever the path, I'm glad to be in sync.

The thing that really supports my interpretation is that I was
looking at our source code when I said that. Whatever the
documentation might not say, the Solaris ld does ignore these
sections, in addition to not passing them to the output. I'm
afraid I really don't know if this was by design, or just
something that happened.

If you think that the GNU interpretation is the right one,
why does that allow ld to ignore such a section when it doesn't
understand the type? If the right behavior is to process it,
but not pass it through, then shouldn't an inability to process
it be an error?

No matter, I'm content for this to be an implementation quirk.
I'd encourage you to stop using it the moment you can safely
remove its use.

- Ali

[Peter Collingbourne]

On Thu, May 24, 2018 at 9:48 PM Ali Bahrami <Ali.B...@oracle.com> wrote:

Coming back around on the sh_link/sh_info aspect of this
discussion...


On 05/23/18 08:53 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> That *might* work for this specific section, but the transition period could be much longer than a year or two (one feature that springs to mind is .gnu.linkonce, which was superseded by COMDAT in the early 2000's but is still supported by the GNU linkers and somewhat by lld, in part because glibc still uses it on i386). On the other hand, there also seem to be good reasons to adopt the rule that I've proposed.

    That really only says that transitions can take a long time,
unless something or someone is able to apply some back pressure
on the issue to flush things out.

The problem with gnu.linkonce as an example is that COMDAT hasn't fully
superseded it. My understanding is that the dwarf sections are not
COMDATified, which means that even when comdat is used, there's
some linkonce handling required. That was discussed here in April:

     https://groups.google.com/forum/#!topic/generic-abi/A-1rbP8hFCA

I hold out hope that linkonce will die a richly deserved death, as I
did (literally) a decade ago, but even now, it's not going to be soon.

My understanding of that thread (and how debug info works generally) is that the DWARF sections currently do not use linkonce or any other fancy linker features at all: the linker just leaves the unused DWARF in the output file (or sufficiently smart ones understand DWARF and can strip out the unused bits). The only reason why any sort of linkonce support exists in lld at all is that we found one object file in glibc that still uses it - nothing else does to the best of my knowledge.

I guess a discussion forum like this one is probably the best way to coordinate back pressure in a multi vendor environment. It may be worth starting a separate discussion on phasing out linkonce, and we can continue discussing the right transition path for linked sections here.

Yeah, I'll probably go for the sh_link then. (But I thought that clearing SHF_INFO_LINK meant that the sh_info is opaque? Though I guess it wouldn't really need to be in sh_info, it could just be stored somewhere in the section itself.)

That all sounds great to me, except for the part about honoring SHF_OPTIONAL being optional (see below).

I'm not really sure how much we need this though --- I sure hope we're not
going to be adding *too* many new sections that reference symbol tables.
This ought to be a fairly rare thing, and maybe something that can just
be handled case by case.

I was thinking that this flag would be used more by platform/toolchain-specific sections than those specified by the gABI, and I'd certainly expect platforms and toolchains to want to do that more frequently than the gABI would.

In fact, we are in the process of adding such a section to clang and lld right now: https://reviews.llvm.org/D44965

The TL;DR is that the section contains a call graph profile that is used by the linker to optimize section layout, and it uses symbol table indexes to refer to functions in the call graph. It seems unclear that this section would be proposed for standardization, at least in its current form, because:

- the sample counts in the call graph are somewhat tied to how the profiling is implemented

- we may want to extend the format in the future.

Now that I think about it, we probably would want this flag in place before changing tools to obey the gABI rules on linked sections. My reasoning is: let's say we change the tools to implement the rules and don't have the flag. That would mean that platforms, toolchains and the gABI would seem to be completely constrained from adding new optional linked sections, as the presence of the new section would cause a good fraction of downstream tools to fail unless the tools are updated in lockstep, and there would be no way to tell the old tools not to fail. That also implies that tools should not be allowed to handle an unknown SHF_OPTIONAL by failing.

[Ali Bahrami]

On 05/25/18 01:44 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Not so sure about the sh_info idea though --- setting
> the sh_link to 0 seems sufficient, and a non-zero sh_info will raise
> other questions.
>
>
> Yeah, I'll probably go for the sh_link then. (But I thought that clearing SHF_INFO_LINK meant that the sh_info is opaque? Though I guess it wouldn't really need to be in sh_info, it could just be stored somewhere in the section itself.)

Sure, that is what SHF_INFO_LINK means. I'm not saying you can't
get away with it.

I meant that the kind of person who studies the gABI may still notice
a non-zero value where the spec doesn't specify any purpose, and ask
questions. Given that you maybe don't need to do this, maybe this is
the final reason not to.

> That all sounds great to me, except for the part about honoring SHF_OPTIONAL being optional (see below).

...

> I was thinking that this flag would be used more by platform/toolchain-specific sections than those specified by the gABI, and I'd certainly expect platforms and toolchains to want to do that more frequently than the gABI would.

...

> That also implies that tools should not be allowed to handle an unknown SHF_OPTIONAL by failing.

I see your point, regarding ABI-specific issues. It's not a
problem for me, because we update our tools together with the
link-editors, so I hadn't thought about it much. Fair enough.

We need some other players to weigh in on this before we rush to
implement, but it seems OK to me.

I don't really understand why SHF_OPTIONAL needs to be more than
a hint. Are you worried that other GNU groups won't do what you
need because the spec doesn't require them to? (Rhetorical: I'm
sure you're not worried about that). The problem isn't enforcement,
it's that currently there's no formal way to make that hint, and
give utilities the license they need to do a discard.

Turning it around, I don't think saying it's mandatory will actually
make anyone implement it. The best way to do that is probably for those
who need it to make the change and contribute it back.

I like not making it mandatory because it allows people to implement
it as they find it useful, rather than having an external timeline
imposed on them by some other group. It's in the spirit of SHF_MERGE,
which provides an option, but not a requirement.

- Ali

[Peter Collingbourne]

I guess it depends on what is meant by "process"... even in a hypothetical linker that rejects sections with unknown types (no linker actually does that, as far as I'm aware -- the GNU linkers and lld all pass unknown sections through, but maybe the Solaris linker doesn't?) you could interpret it to mean:

1) read special sections

2) discard on SHF_EXCLUDE

3) error out on unknown section types

But that's really a semantics quibble and I'm happy to let this one go.

Peter

No matter, I'm content for this to be an implementation quirk.
I'd encourage you to stop using it the moment you can safely
remove its use.

- Ali

[Peter Collingbourne]

Right now I'm not worried about GNU/LLVM tools (at least on the non-technical side). I guess I was a little more concerned about non-mainstream tools not implementing the needed behaviour. But in that case I imagine that the onus is more on the tools to adapt to the compilers rather than the other way around, so maybe it wouldn't be a huge issue in practice.

Peter

I like not making it mandatory because it allows people to implement
it as they find it useful, rather than having an external timeline
imposed on them by some other group. It's in the spirit of SHF_MERGE,
which provides an option, but not a requirement.

- Ali

[Ali Bahrami]

On 05/25/18 02:48 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> Right now I'm not worried about GNU/LLVM tools (at least on the non-technical side). I guess I was a little more concerned about non-mainstream tools not implementing the needed behaviour. But in that case I imagine that the onus is more on the tools to adapt to the compilers rather than the other way around, so maybe it wouldn't be a huge issue in practice.

Sure. Ultimately, if they don't see a need for it, it doesn't
hurt anyone else to leave them to it.

- Ali

[ben.dunbobb...@gtempaccount.com]

Thanks for the proposal Peter.

De-duplication (our analogue of gold's --icf) is very important to our

users. We have customers that are now making heavy use of code

generators and relying on this feature to remove the duplicated bytes.

Ali suggested:

"""
Pulling all of those threads together, I think that
defining an SHT_SYMATTR section, defined as an
array of words containing flag bits to augment symbols,
would be very useful for the gABI, as well as offering
a solution to your immediate problem. Such a flag array
would be associated to its symbol table with sh_link,
and the first flag defined would be:
#define SYMATTR_FLG_ADDRSIG
"""

I wonder if we could expand on this idea further. I think it would be very

useful to have a section type that allows binary tools to understand that

this section contains a table of entries that associate metadata with

symbols via the symbol index.

I am thinking of the .stack_sizes section. This is currently a monolithic

section (one per object file) which contains an array of entries where

each entry is the address of the function (computed via a relocation)

and a uleb128 containing the stack size for that function. 

http://lists.llvm.org/pipermail/llvm-dev/2017-August/117028.html
https://reviews.llvm.org/D39788

On our platform the linker edits the contents of this section
during linking to account for discarded comdats, dead-stripping
(roughly --gc-sections in gold), weak symbols, and
de-duplication (roughly --icf in gold). As mentioned here:

https://groups.google.com/d/msg/generic-abi/A-1rbP8hFCA/EDA7Sf3KBwAJ

We would like to use elf features to emit this section in such a
way that the linker does not have to have special case code to
understand the contents of the section. With the current standard
the way to do this is to use -ffunction-sections to put each function
into its own section and to emit the .stack_sizes entry for each
function into its own matching section. Then we can use
SHF_LINK_ORDER to allow linkers to throw away the .stack_sizes
information if the corresponding function is discarded.

The problem with this is overhead. In a real piece of customer code
(millions of lines of C++) I measured that the monolithic section version
of .stack_sizes cost about 0.2% of the object file space, in comparison
the section-per-function approach cost about 2%.

If the gabi defined had a way of representing a table of symbol
information then linkers could edit that table to account for decisions
at link time (dead-stripping, de-duplication, weak symbols, and
discarded comdats) in a more efficient way.

To make this less theoretical here is a concrete proposal: I propose
defining an SHT_SYM_INFO section which is an array of sh_entsize
entries with the same number of entries as there are symbol table
entries in the symbol table associated via the sections sh_link field.
The interpretation of each entry is defined by the sh_info field. If the
sh_info field is INFO_SYMATTR (0x1) then each entry is interpreted
as a set of flag bits (currently there is only one recognized flag
ADDRSIG (0x1). If the section is marked as SHF_EXCLUDE then
it is consumed by the linker and the information contained may be
used during the link process but the section does not contribute to
the output file directly. Otherwise, the linker copies the entries from
the input sections to the output sections in the order that the
equivalent symbol appears in the output .symtab. Entries that
correspond to references, or to symbols that the link editor has
discarded, are removed.

[Peter Collingbourne]

Hi Ben,

Thanks for that proposal.

High level thought: It may be worth doing something like that, but I have a number of concerns around introducing a generic mechanism for symbol attributes, and there seem to be good reasons for the generic mechanism to be considered separately. So I don't think we should let ADDRSIG get side-tracked by these concerns, and it should probably be a separate proposal.

In more detail: something like your proposal may be reasonable for attributes that are intended to be passed through and consumed by tools reading the executable (such as stack_sizes), but it's not clear that we want to specify any sort of generic behaviour around sections that are intended to be consumed by the linker (such as ADDRSIG). In particular, the behaviour of choosing the attribute for the prevailing symbol wouldn't be correct for ADDRSIG because we also need to merge attributes from undefined and non-prevailing symbols, and it's not clear that any specific behaviour that we choose would be correct for any other attributes either (this behaviour would come into play even for SHF_EXCLUDE sections because of ld -r). And indeed, there doesn't seem to be much value in specifying a behaviour for sections consumed by the linker at the gABI level, because the linker behaviour for such sections would already be determined by whatever specifies the section itself (either the gABI or the platform/toolchain-specific ABI).

We'd also need to specify what happens with symbols that do not have a corresponding symbol attribute (either because they are linker-defined, DSO-defined or simply come from an object that lacks the attribute section). We could just fill the symbol's part of the attribute section with zeros I suppose, and the consumer would need to recognize that as meaning "attribute not present". This seems like another point in favour of this not being the right thing to do for linker-consumed sections, because the zeros would not necessarily be valid or correct content for a linker-consumed section piece, and it's possible for the zeros to be introduced in such a way that they will later be indistinguishable from the attribute not being present to begin with (imagine that I use ld -r to combine an object with the attribute section with an object without the section).

Peter

--

[ben.dunbobb...@gtempaccount.com]

Thanks Peter. I used SHF_EXCLUDE incorrectly in my proposal. As you point out,
we wouldn't want the semantics for SHF_EXCLUDE. What I actually wanted was a
flag to indicate whether any tools that rewrite the symbol table need to consume
and rewrite the symbol metadata section or whether a simple rule like "choose
the prevailing symbol" is appropriate. My idea was that we could have a section
with a common structure and a set of default rules:

1. If a symbol is stripped then strip the corresponding entry.

2. Choose the metadata for the prevailing symbols when combining objects.

However, for section contents that are not handled correctly by these default rules we
would set a flag on the section which would indicate to the tools that they
are required to rewrite the section if they are editing the associated symbol
table. In this case e.g. "ld -r" would have to consume the attributes in the
input symbol attributes sections and create an appropriate symbol metadata
section that matches the .symtab in the output.

Your second set of objections about what to do regarding empty entries is
difficult. In fact I think it would be better to define such a section as a set
of index and payload pairs rather than a sparse array which would both reduce
the section size and sidestep those problems.

Having thought about your response it does seem that the different use cases
will not combine naturally. Therefore, I agree that it would be better to make a
separate proposal and keep the proposal here as minimal as possible to keep
SHT_ADDRSIG on track.

So getting back to SHT_ADDRSIG one of the objections seems to be the use of
ulebs. Is this really a reasonable objection? What would the overhead be for
using a fixed width type for the symbol table indexes?

[Peter Collingbourne]

On Wed, May 30, 2018 at 2:46 PM ben.dunbobbin%sony.com via Generic System V Application Binary Interface <gener...@googlegroups.com> wrote:

Thanks Peter. I used SHF_EXCLUDE incorrectly in my proposal. As you point out,
we wouldn't want the semantics for SHF_EXCLUDE. What I actually wanted was a
flag to indicate whether any tools that rewrite the symbol table need to consume
and rewrite the symbol metadata section or whether a simple rule like "choose
the prevailing symbol" is appropriate. My idea was that we could have a section
with a common structure and a set of default rules:

1. If a symbol is stripped then strip the corresponding entry.

2. Choose the metadata for the prevailing symbols when combining objects.

However, for section contents that are not handled correctly by these default rules we
would set a flag on the section which would indicate to the tools that they
are required to rewrite the section if they are editing the associated symbol
table. In this case e.g. "ld -r" would have to consume the attributes in the
input symbol attributes sections and create an appropriate symbol metadata
section that matches the .symtab in the output.

Your second set of objections about what to do regarding empty entries is
difficult. In fact I think it would be better to define such a section as a set
of index and payload pairs rather than a sparse array which would both reduce
the section size and sidestep those problems.

The index/payload representation would certainly make sense for sparse mappings or in cases where it wouldn't make sense to synthesize a zero sentinel value, but I was under the impression that on platforms that use it, stack_sizes would be dense since essentially every function symbol would have a stack_size, so a section mapped onto the symbol table would probably be more compact. So absent other considerations it may be better to use a mapped section with a sentinel value for that use case.

These sorts of considerations lead me to think that it may be premature to add such a generic feature to the gABI: we'd probably want to see one or two more use cases (i.e. the "rule of three" principle) before adding anything.

Having thought about your response it does seem that the different use cases
will not combine naturally. Therefore, I agree that it would be better to make a
separate proposal and keep the proposal here as minimal as possible to keep
SHT_ADDRSIG on track.

So getting back to SHT_ADDRSIG one of the objections seems to be the use of
ulebs. Is this really a reasonable objection?

I don't really see it as a good objection on its own: simply because we haven't used ulebs before for anything else isn't a good reason not to start using them. We should be free to use whatever representation makes sense for the particular use case (see also: SHT_RELR).

 

What would the overhead be for
using a fixed width type for the symbol table indexes?

I've collected numbers on the overhead for this as well as Ali's suggestion of an attribute section mapped onto the symbol table. I'll reply separately to his earlier message with the numbers.

Peter

[Peter Collingbourne]

I've implemented SHT_SYMATTR, both compressed and uncompressed variants, and measured the impact on object file size for clang. I also looked at storing words in the SHT_ADDRSIG section instead of ulebs. For reference, here are my implementations:

https://github.com/pcc/llvm-project/tree/llvm-addrsig1 - SHT_ADDRSIG, ulebs

https://github.com/pcc/llvm-project/tree/llvm-addrsig2 - SHT_SYMATTR, compressed

https://github.com/pcc/llvm-project/tree/llvm-addrsig3 - SHT_SYMATTR, uncompressed

https://github.com/pcc/llvm-project/tree/llvm-addrsig4 - SHT_ADDRSIG, words

The object file size overheads are:

SHT_ADDRSIG, ulebs: 0.08%

SHT_SYMATTR, compressed: 0.11%

SHT_SYMATTR, uncompressed: 1.07%

SHT_ADDRSIG, words: 0.10%

My conclusion straight away from these numbers is that uncompressed SHT_SYMATTR is not an option if we can avoid it: the object file size overhead is simply too large. But compressed SHT_SYMATTR seems worth considering since the additional object file size cost is only 0.03%. The additional cost of words in SHT_ADDRSIG is only 0.02%, but that's a cost that doesn't really buy us much other than avoiding the use of a novel representation, and as I was saying elsewhere on the thread I'm not convinced that that's worth much.

My other concern for SHT_SYMATTR was the effect on link time. Keep in mind that at the end of the day the linker doesn't want to know which symbols are address-significant, it only needs to know which sections are address-significant. That means that the linker needs to do a second pass over the address-significant symbols once symbol resolution is done to mark sections as address-significant based on the symbol resolutions. This is straightforward if the representation is a list of indexes: we simply need to visit the symbol at each index in the list and mark its section as address-significant. But with SHT_SYMATTR we have to revisit every symbol in every object file after symbol resolution to copy the address-significant bit onto the section. And with compression we have to pay the cost of decompressing the sections as well.

So I also implemented compressed SHT_SYMATTR in the linker and measured the effect on link time. The median wall-clock link time for 500 links of clang with --icf=safe was 0.97s with ulebs in SHT_ADDRSIG, or 0.98s with compressed SHT_SYMATTR. So the link time cost of SHT_SYMATTR is around 1%. That seems acceptable to me, but I'd like to get other opinions as well.

Peter

[Ali Bahrami]

On 05/31/18 05:48 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> My conclusion straight away from these numbers is that uncompressed SHT_SYMATTR is not an option if we can avoid it: the object file size overhead is simply too large. But compressed SHT_SYMATTR seems worth considering since the additional object file size cost is only 0.03%. The additional cost of words in SHT_ADDRSIG is only 0.02%, but that's a cost that doesn't really buy us much other than avoiding the use of a novel representation, and as I was saying elsewhere on the thread I'm not convinced that that's worth much.

To my eye, a cost of 0.03% says that these things have essentially
the same cost, and since I think avoiding the use of a novel representation
is actually a very big deal, this looks great to me. (I'll tackle the uleb
thing separately).

And don't forget that we get 31-bits of unused future symbol
attributes out of the deal, which seems a really nice bonus.

>
> My other concern for SHT_SYMATTR was the effect on link time. Keep in mind that at the end of the day the linker doesn't want to know which symbols are address-significant, it only needs to know which sections are address-significant. That means that the linker needs to do a second pass over the address-significant symbols once symbol resolution is done to mark sections as address-significant based on the symbol resolutions. This is straightforward if the representation is a list of indexes: we simply need to visit the symbol at each index in the list and mark its section as address-significant. But with SHT_SYMATTR we have to revisit every symbol in every object file after symbol resolution to copy the address-significant bit onto the section. And with compression we have to pay the cost of decompressing the sections as well.

Does this really have to be 2 passes?

Logically speaking, the symbol table and symattr combine to form
a single symbol table. You can think of it as adding an extra
field to Elf_Sym, only it's in a separate array. Get both
and pass them both to symbol resolution.

Now, during symbol resolution, when an ADDRSIG reference symbol
is resolved to a definition symbol, you transfer the ADDRSIG attribute
to the section. When symbol resolution is done, all the ADDRSIG
sections will be tagged.

>
> So I also implemented compressed SHT_SYMATTR in the linker and measured the effect on link time. The median wall-clock link time for 500 links of clang with --icf=safe was 0.97s with ulebs in SHT_ADDRSIG, or 0.98s with compressed SHT_SYMATTR. So the link time cost of SHT_SYMATTR is around 1%. That seems acceptable to me, but I'd like to get other opinions as well.

It seems OK to me too, but if that really involves a second pass on
the symbols, I bet you can squeeze it a bit more.

- Ali

[Ali Bahrami]

I want to explain my concerns about uleb. This is
a bit long, so I'll understand if most folks skip it,
but I want to be sure that if you disagree with me, that
it's for the right reasons. :-)

On 05/31/18 04:26 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> So getting back to SHT_ADDRSIG one of the objections seems to be the use of
> ulebs. Is this really a reasonable objection?
>
>
> I don't really see it as a good objection on its own: simply because we haven't used ulebs before for anything else isn't a good reason not to start using them. We should be free to use whatever representation makes sense for the particular use case (see also: SHT_RELR).

That's not a good objection, but it's also not the objection I'm
raising. It is wrong to say that you can't use something just because
it hasn't been used before. You certainly can, but maybe if it duplicates
existing things, or complicates what used to be simple, the specific
benefit isn't worth the overall rise in complexity. What if you can find
an alternative that doesn't require doing that? Isn't that better?

If you read the RELR case, you'll note that I raised some similar
concerns about complexity. But while RELR does do something that normal
relocations can do, it doesn't alter the basic ways in which the
ELF format is interpreted. It doesn't introduce a new integer encoding,
it just introduces a new struct that is interpreted in the usual ways.
With RELR, we stripped away some unnecessary complications and ended up
being improved over the original proposal. Best of all RELR is completely
optional to the link-editor, so no one is forced to do it. It's a
pure option, and it fit well enough that I was able to see it as a
win.

You say we should be free to use whatever representation makes sense.
That's true enough, but gABI is a shared commons. Suppose that we don't
all agree about which representation makes more sense? Whose freedom are you
referring to then? :-) At this level, we're balancing multiple
concerns, and looking for "mutually agreeable and free enough".

So back to uleb... The reason I don't think uleb is a great fit to core ELF
is that it makes a number of choices that are not aligned with what the
rest of the core ELF format does. Good formats (software generally) are
marked as much by what they leave out, as by what they include. The best
systems are small, and have relatively few variations on their core themes.
A small number of patterns seem to apply in many different situations. ELF
has gotten a bit gothic in places, but its done well for something in its
fourth decade. These are important decisions that affect whether ELF will
still be comprehensible in the decades to come. Longevity is not always
important in software, but it's really important to object formats. This
stuff needs to last forever. So it's necessary, and generally annoying,
to ask some hard "does it fit" questions.

Here is a (severely incomplete) list of some general characteristics
of the core ELF format:

- Byte order is specified in the ELF header

- Numbers are represented as plain (unsigned) integers
of fixed width (mainly 32-bit), often in arrays.

- Endian issues are managed by libelf, by applying
xlate on sections as they are input/output, driven
by the ELF header, and the platform on which libelf
is executing. This is the only decoding overhead to
accessing data, and only paid if the object and running
machine have differing byte orders.

- All (I think) of the important items (sections, symbols)
are counted using the 32-bit Elfxx_Word type.

- Arrays support efficient direct access, which means that
the elements are not variable size, and that you do not
need to decode all the elements from the start of a
section to reach the nth item.

uleb is a cool format also, but most of its characteristics
feature choices that don't align with the ELF characteristics
above:

- Byte order is implicit in uleb, not controlled by
the ELF header.

- Items are variable length, which might make for smaller
sections (maybe not always, but let's just agree that
they're generally smaller).

- uleb 128 can represent numbers that are out of bounds for
the ELF type (symbol index) being discussed here. (Not
super important, but it's a mismatch of the type system).

- Efficient direct access is not supported, and any access
comes with decoding overhead.

Please note that I don't say any of that is intrinsically bad.
What I am saying is that it's not very ELF-like. Rather than fitting
into the existing system, and making everything that much better,
it creates a special one off case, and defies some normal ELF expectations,

- Ali

[Cary Coutant]

> The proposal is that we introduce a new section type, SHT_ADDRSIG. This
> section would contain a ULEB128-encoded sequence of symbol table indexes
> corresponding to address-significant symbols. If the section is not present
> in an object file, all symbols in the object file are treated as address
> significant. For compatibility with existing tools, the section would be
> marked with a flag SHF_EXCLUDE to ensure that it is dropped by linkers which
> do not recognize the section.

The "Address-significant" property is a constraint imposed by a
reference to the symbol, not an intrinsic property of the symbol or
its section. If x86 had distinct relocation types for function pointer
relocations (as, e.g., PA-RISC and Itanium do), we would not have
needed all the guess-work that's in place for ICF to decide whether a
particular reference is a function pointer.

A much simpler (and zero-cost, from an object file size point of view)
solution would be to add FPTR relocations to the psABI, and use those
for any references that would impose the address significance
constraint.

-cary

[Peter Collingbourne]

On Thu, May 31, 2018 at 9:28 PM Ali Bahrami <Ali.B...@oracle.com> wrote:

On 05/31/18 05:48 PM, 'Peter Collingbourne' via Generic System V Application Binary Interface wrote:
> My conclusion straight away from these numbers is that uncompressed SHT_SYMATTR is not an option if we can avoid it: the object file size overhead is simply too large. But compressed SHT_SYMATTR seems worth considering since the additional object file size cost is only 0.03%. The additional cost of words in SHT_ADDRSIG is only 0.02%, but that's a cost that doesn't really buy us much other than avoiding the use of a novel representation, and as I was saying elsewhere on the thread I'm not convinced that that's worth much.

    To my eye, a cost of 0.03% says that these things have essentially
the same cost, and since I think avoiding the use of a novel representation
is actually a very big deal, this looks great to me. (I'll tackle the uleb
thing separately).

And don't forget that we get 31-bits of unused future symbol
attributes out of the deal, which seems a really nice bonus.

Agreed that they're basically the same cost, and a reasonable one to pay by default. I think your separate mail on ulebs makes some good points, though I'm not 100% convinced (I'll try to find some time to reply separately). I'm also agreed on the second para about 31 bits of unused symbol attributes. So I think I'm happy with compressed SHT_SYMATTR.

>
> My other concern for SHT_SYMATTR was the effect on link time. Keep in mind that at the end of the day the linker doesn't want to know which symbols are address-significant, it only needs to know which sections are address-significant. That means that the linker needs to do a second pass over the address-significant symbols once symbol resolution is done to mark sections as address-significant based on the symbol resolutions. This is straightforward if the representation is a list of indexes: we simply need to visit the symbol at each index in the list and mark its section as address-significant. But with SHT_SYMATTR we have to revisit every symbol in every object file after symbol resolution to copy the address-significant bit onto the section. And with compression we have to pay the cost of decompressing the sections as well.

Does this really have to be 2 passes?

Logically speaking, the symbol table and symattr combine to form
a single symbol table. You can think of it as adding an extra
field to Elf_Sym, only it's in a separate array. Get both
and pass them both to symbol resolution.

Now, during symbol resolution, when an ADDRSIG reference symbol
is resolved to a definition symbol, you transfer the ADDRSIG attribute
to the section. When symbol resolution is done, all the ADDRSIG
sections will be tagged.

It's true that it doesn't need to be two passes if you implement it that way. But you do end up accessing the same amount of data, just in a different order (it's possible that the new approach would help with memory locality, though). It also wasn't the first implementation that sprung to mind, as it means that the linker's data structures become slightly more complicated (due to needing to store the ADDRSIG bit on symbols), which can lead to bugs -- I was specifically thinking about how weak/strong resolution, --wrap, --defsym and linker scripts would interact with the feature. With the two pass approach, doing the right thing falls out naturally, as long as the second pass happens in the right place.

>
> So I also implemented compressed SHT_SYMATTR in the linker and measured the effect on link time. The median wall-clock link time for 500 links of clang with --icf=safe was 0.97s with ulebs in SHT_ADDRSIG, or 0.98s with compressed SHT_SYMATTR. So the link time cost of SHT_SYMATTR is around 1%. That seems acceptable to me, but I'd like to get other opinions as well.

It seems OK to me too, but if that really involves a second pass on
the symbols, I bet you can squeeze it a bit more.

It may be possible, but first I'd like to see how much of the cost comes from the additional pass and how much comes from decompression. It should be possible to measure that by not compressing the SHT_SYMATTR sections to begin with.

Peter

[H.J. Lu]

New relocations have been added to x86 psABI to implement linker relaxation,
I don't see why we can't do it for ICF.

--
H.J.

[Peter Collingbourne]

It's true that address-significance can technically be considered a property of a reference, but that doesn't necessarily mean that we need to represent it in object files that way. A few points:

1) I'm not convinced that this approach would be simpler overall, because it would impose additional costs elsewhere:

- it would mean updating every psABI to add the new FPTR relocations, as well as relocations that mean the opposite of FPTR (the latter being required because we would like a way to say that in C++, vtables and virtual function pointers are not address-significant, as well as a way of saying the same about compiler-generated data structures and similar constructs in other languages). That would mean adding significant redundancy to every psABI.

- because old linkers would not recognize the new relocations, the feature would be need to be behind a flag and off by default, so it would be less discoverable, at least to begin with

- linkers would need to recognize that all non-FPTR relocations in old object files are address-significant, so we'd need some sort of marker on new object files anyway (although I guess we could avoid this by redefining the existing relocations to be FPTR and having the new ones be non-FPTR).

- depending on how the linker is implemented, it could make things more complicated, because now it needs to read all relocations before running ICF. lld does not do this for example (if ICF is enabled, the first time it reads relocations might be *during* ICF).

2) There is not necessarily a 1:1 mapping between relocations and address-significance properties. Consider:

__attribute__((visibility("hidden"))) void *f() {

  return f;

}

In many architectures with PC-relative addressing, the function's reference to itself can be relaxed away, so this function could end up with no relocations at all. To avoid this we would need to teach assemblers to avoid relaxing such relocations, which could make them more complicated and could make object files larger (although admittedly only in some far-fetched cases).

Consider also this example presented upthread:

void f1();

void f2();

typedef void (*fp)();

static fp p(bool b) {

  return b ? f1 : f2;

}

void f(bool b) {

  p(b)();

}

In this example, neither f1 nor f2 are address-significant because although the address leaks from a static function, it does not leak from the translation unit. Adding another function:

fp g(bool b) {

  return p(b);

}

makes f1 and f2 address-significant, but it cannot be attributed to a specific relocation, so a compiler would probably need to arrange for the address-significance to be moved onto the section for the function p.

3) It's not clear that there would be a benefit in representing address-significance using relocations instead of a symbol property.

In a traditional link (without --gc-sections) it normally wouldn't provide a benefit because each symbol in an object file would typically either be defined or have one or more relocations associated with it, so it wouldn't matter if the address-significance is expressed via the relocation or via the symbol. But let's assume that the user has --gc-sections enabled, since if they're using ICF they probably care a lot about binary size. In that case, we gain a benefit if a translation unit contains an address-significance that would have been optimized away by --gc-sections. Although I'm somewhat sceptical that this would provide a benefit, I'd be happy to run an experiment to get a rough idea of how much it would help in practice. Specifically, I can change lld to only respect an address-significance property on a symbol if at least one of the sections in the object file containing a relocation to the symbol is live per --gc-sections. (I probably can't do better than that for now because LLVM's address-significance tracking only works on a per-TU basis. This also wouldn't be sound because of the self-reference issue.) Then I'll measure the binary size of clang with and without this.

Also keep in mind that even if a representation based on references turn out to be beneficial, we don't necessarily need to use relocations. We could always represent it with some sort of separate mapping from sections to the symbols that they make address-significant. That would address my concerns in 1 and 2.

Peter

 

-cary

[Cary Coutant]

> It's true that address-significance can technically be considered a property
> of a reference, but that doesn't necessarily mean that we need to represent
> it in object files that way. A few points:

It's always a sound practice to have the representation a close fit to
the model. If something is a property of the reference, it should be
reflected in the relocation.

> 1) I'm not convinced that this approach would be simpler overall, because it
> would impose additional costs elsewhere:
>
> - it would mean updating every psABI to add the new FPTR relocations, as
> well as relocations that mean the opposite of FPTR (the latter being
> required because we would like a way to say that in C++, vtables and virtual
> function pointers are not address-significant, as well as a way of saying
> the same about compiler-generated data structures and similar constructs in
> other languages). That would mean adding significant redundancy to every
> psABI.

I don't see where you're getting this redundancy. The non-FPTR
relocations already exist.

> - because old linkers would not recognize the new relocations, the feature
> would be need to be behind a flag and off by default, so it would be less
> discoverable, at least to begin with

Not necessarily. Compilers are constantly relying on new features of
the assembler, linker, and other tools, and compiler distros will
include the tools that support those new features. We've added new
relocations to the x86 psABI (and others) several times without any
trouble.

> - linkers would need to recognize that all non-FPTR relocations in old
> object files are address-significant, so we'd need some sort of marker on
> new object files anyway (although I guess we could avoid this by redefining
> the existing relocations to be FPTR and having the new ones be non-FPTR).

That would be fine, although I'd also be fine with leaving the
existing guesswork in place for a time.

> - depending on how the linker is implemented, it could make things more
> complicated, because now it needs to read all relocations before running
> ICF. lld does not do this for example (if ICF is enabled, the first time it
> reads relocations might be *during* ICF).

I don't see a problem there. ICF can't function without reading the
relocations, but I don't see why it would need to have collected this
information before starting.

> 2) There is not necessarily a 1:1 mapping between relocations and
> address-significance properties. Consider:
>
> __attribute__((visibility("hidden"))) void *f() {
> return f;
> }
>
> In many architectures with PC-relative addressing, the function's reference
> to itself can be relaxed away, so this function could end up with no
> relocations at all. To avoid this we would need to teach assemblers to avoid
> relaxing such relocations, which could make them more complicated and could
> make object files larger (although admittedly only in some far-fetched
> cases).

For this far-fetched case, I'm quite happy with a requirement that a
relocation must remain.

> Consider also this example presented upthread:
>
> void f1();
> void f2();
> typedef void (*fp)();
> static fp p(bool b) {
> return b ? f1 : f2;
> }
> void f(bool b) {
> p(b)();
> }
>
> In this example, neither f1 nor f2 are address-significant because although
> the address leaks from a static function, it does not leak from the
> translation unit. Adding another function:
>
> fp g(bool b) {
> return p(b);
> }
>
> makes f1 and f2 address-significant, but it cannot be attributed to a
> specific relocation, so a compiler would probably need to arrange for the
> address-significance to be moved onto the section for the function p.

Proving that a function pointer doesn't leak is a complicated
data-flow problem. If the compiler isn't prepared to analyze the data
flow for the entire translation unit, it must pessimize the references
to f1 and f2. I don't see how using relocations vs. symbol attributes
makes this any different.

> 3) It's not clear that there would be a benefit in representing
> address-significance using relocations instead of a symbol property.
>
> In a traditional link (without --gc-sections) it normally wouldn't provide a
> benefit because each symbol in an object file would typically either be
> defined or have one or more relocations associated with it, so it wouldn't
> matter if the address-significance is expressed via the relocation or via
> the symbol. But let's assume that the user has --gc-sections enabled, since
> if they're using ICF they probably care a lot about binary size. In that
> case, we gain a benefit if a translation unit contains an
> address-significance that would have been optimized away by --gc-sections.

This is indeed one reason why it's better to let the relocations
describe the reference.

> Also keep in mind that even if a representation based on references turn out
> to be beneficial, we don't necessarily need to use relocations. We could
> always represent it with some sort of separate mapping from sections to the
> symbols that they make address-significant. That would address my concerns
> in 1 and 2.

That would be far worse in my estimation, especially considering the
lengths you've gone to upthread to add parallel symbol table sections,
or other sections that reference the symbol table. I'd like to keep
such complications out of the gABI -- one SHT_SYMTAB_SHNDX section is
one too many already.

-cary

[Peter Collingbourne]

On Tue, Jun 5, 2018 at 4:19 PM Cary Coutant <ccou...@gmail.com> wrote:

> It's true that address-significance can technically be considered a property
> of a reference, but that doesn't necessarily mean that we need to represent
> it in object files that way. A few points:

It's always a sound practice to have the representation a close fit to
the model. If something is a property of the reference, it should be
reflected in the relocation.

That might be true in general, and if we could add a field to Elf_Rela the tradeoffs may be different. But we can't, so either we're stuck putting something in every psABI or we can consider other options.

> 1) I'm not convinced that this approach would be simpler overall, because it
> would impose additional costs elsewhere:
>
> - it would mean updating every psABI to add the new FPTR relocations, as
> well as relocations that mean the opposite of FPTR (the latter being
> required because we would like a way to say that in C++, vtables and virtual
> function pointers are not address-significant, as well as a way of saying
> the same about compiler-generated data structures and similar constructs in
> other languages). That would mean adding significant redundancy to every
> psABI.

I don't see where you're getting this redundancy. The non-FPTR
relocations already exist.

I meant that for each relocation type that can result from user code we would need 2 relocations where there would previously be 1, depending on whether we define the existing relocation as FPTR or non-FPTR. I can think of at least 4 relocation types which would need to be duplicated in x86-64: R_X86_64_32, R_X86_64_PC32, R_X86_64_GOTPCREL and R_X86_64_64. The same goes for every such type of reference on every architecture -- I'm not even sure how many additional relocation types would be required on ARM for example.

> - because old linkers would not recognize the new relocations, the feature
> would be need to be behind a flag and off by default, so it would be less
> discoverable, at least to begin with

Not necessarily. Compilers are constantly relying on new features of
the assembler, linker, and other tools, and compiler distros will
include the tools that support those new features. We've added new
relocations to the x86 psABI (and others) several times without any
trouble.

That might work if you can guarantee that the producer of the object file is revlocked to the consumer. That may be the case with GNU binutils, because GNU as will generally have the same version as GNU ld, but it isn't the case with clang because it has its own assembler and it doesn't know which linker will be used. GOTPCRELX is still disabled by default in clang for this reason, for example.

> - linkers would need to recognize that all non-FPTR relocations in old
> object files are address-significant, so we'd need some sort of marker on
> new object files anyway (although I guess we could avoid this by redefining
> the existing relocations to be FPTR and having the new ones be non-FPTR).

That would be fine, although I'd also be fine with leaving the
existing guesswork in place for a time.

> - depending on how the linker is implemented, it could make things more
> complicated, because now it needs to read all relocations before running
> ICF. lld does not do this for example (if ICF is enabled, the first time it
> reads relocations might be *during* ICF).

I don't see a problem there. ICF can't function without reading the
relocations, but I don't see why it would need to have collected this
information before starting.

You're right that it doesn't create a requirement to read the relocations before ICF, but not doing so may increase implementation complexity. In lld we currently decide up front whether sections are eligible for ICF without looking at relocations. An example of an ineligible section is a writable section or a section in the .init output section. If so, we add them to a list of ICFable sections and run ICF on those sections. With this proposal, we need a second category of ineligible sections: sections that have been identified as being ineligible during ICF. And because ICF is multi-threaded, we would need to collect that information in a thread-safe way.

That's fair.

> 3) It's not clear that there would be a benefit in representing
> address-significance using relocations instead of a symbol property.
>
> In a traditional link (without --gc-sections) it normally wouldn't provide a
> benefit because each symbol in an object file would typically either be
> defined or have one or more relocations associated with it, so it wouldn't
> matter if the address-significance is expressed via the relocation or via
> the symbol. But let's assume that the user has --gc-sections enabled, since
> if they're using ICF they probably care a lot about binary size. In that
> case, we gain a benefit if a translation unit contains an
> address-significance that would have been optimized away by --gc-sections.

This is indeed one reason why it's better to let the relocations
describe the reference.

It's an as-yet hypothetical reason why it may be better. I want to see whether it makes a real difference in practice first. If so, it may be worth doing something about it.

 

> Also keep in mind that even if a representation based on references turn out
> to be beneficial, we don't necessarily need to use relocations. We could
> always represent it with some sort of separate mapping from sections to the
> symbols that they make address-significant. That would address my concerns
> in 1 and 2.

That would be far worse in my estimation, especially considering the
lengths you've gone to upthread to add parallel symbol table sections,
or other sections that reference the symbol table. I'd like to keep

such complications out of the gABI -- one SHT_SYMTAB_SHNDX section is
one too many already.

I haven't fully thought through the design, but it may be possible to come up with one that fits in the gABI. (And again, it's conditioned on being beneficial.)

As we discussed, the processing around sections that reference the symbol table seems to be necessary to strip Solaris object files correctly already, so it doesn't seem like a huge additional burden. We also discussed other use cases for platform/toolchain-specific sections that reference the symbol table, some of which we're already starting to implement in LLVM.

Or is it your position that it shouldn't be possible to write a strip tool that works with all gABI compliant object files?

[Florian Weimer]

On 06/01/2018 07:13 AM, Ali Bahrami wrote:
> Please note that I don't say any of that is intrinsically bad.

But it is! uleb is unnecessarily hard to decode because the first byte
does not tell you the length of the entire number. Sure, you can
probably decode it fairly efficiently with fancy vector instructions,
but it could have been so much easier, with pretty much identical
storage requirements.

Something like UTF-8 would be far more preferable.

Thanks,
Florian

[Peter Collingbourne]

There was an interesting discussion a while back about variable-length integer encodings in the WebAssembly format:

https://github.com/WebAssembly/design/issues/601

One of the encodings (PrefixVarint) can be decoded using at most a single branch and was measured to be significantly faster than ulebs.

They ultimately went for ulebs due to familiarity among other reasons, but if there ever were a strong reason to add variable-length integers to core ELF we might want to consider one of these other encodings.

Peter

Thanks,
Florian

[Ali Bahrami]

Hi Florian,

My complaint is with the idea of deviating from the normal ELF representation of integers at all, rather than about uleb specifically. I would probably agree with you about a UTF-8 style encoding being better than uleb, but I wouldn't be any happier to see it used in core ELF.

- Ali