Proposal: Add new dynamic symbol table hash to ELF standard

[Cary Coutant]

The current discussion leading from Carlos' question about why DT_HASH
is mandatory leads me to wonder why we shouldn't update the ELF
standard with what is clearly a better hash algorithm. After all, we
added support for the ZSTD compression algorithm.

I would propose taking the current DT_GNU_HASH design pretty much as
is and adding it to the ELF standard as DT_HASH_2. The GNU hash table
imposes certain additional ordering requirements on the dynamic symbol
table, but there is benefit in dynamic loader performance, I believe.

At the same time, we would add DT_SYMTABSZ (or, equivalently,
DT_SYMTAB_COUNT) to the dynamic table to make it possible to know the
number of symbols without consulting the hash table.

We would mandate that the dynamic table must contain at least one of
DT_SYMTABSZ or DT_HASH (i.e., if using the new hash table only,
DT_SYMTABSZ would be required). With DT_SYMTABSZ, both hash tables
would be optional.

My only concern is whether the DJB hash algorithm used by DT_GNU_HASH
is encumbered by any license (even GPL). It dates to 1991, and I've
seen it around enough (we even use it in the DWARF standard) that I
suspect it and its common implementation are public domain. Can anyone
confirm this?

-cary

[Fangrui Song]

Thanks for creating this proposal. There are two parts:

* DT_SYMTABSZ / DT_SYMTAB_COUNT
* #define DT_HASH_2 0x6ffffef5 /* comment? */

I favor both.

I prefer DT_SYMTAB_COUNT over DT_SYMTABSZ because the count is more
commonly used and consumers can avoid a division by a constant integer.

For DT_HASH_2, we need an associated SHT_* value in the generic range and
a recommended name in ch4.sheader.html "Special Sections".

From the naming, it seems that we should use SHT_HASH_2 and .hash_2 ?
The naming looks good to me.

---

My reply at
https://groups.google.com/g/generic-abi/c/th5919osPAQ/m/tkTx6br9AwAJ
has mentioned my viewpoint. If an OS doesn't like the proposal, I think
it makes no sense to change linkers to use ELFOSABI_GNU just for the
GNU-style hash table.

[Ian Lance Taylor]

On Thu, Aug 11, 2022 at 10:26 AM Cary Coutant <ccou...@gmail.com> wrote:

My only concern is whether the DJB hash algorithm used by DT_GNU_HASH
is encumbered by any license (even GPL). It dates to 1991, and I've
seen it around enough (we even use it in the DWARF standard) that I
suspect it and its common implementation are public domain. Can anyone
confirm this?

I got curious enough to look for his original post, which appears to be this: 

https://groups.google.com/g/comp.lang.c/c/VByoIO8GySs/m/2XN9iGTpgmsJ 

I'm not a lawyer, of course, but it seems to me that there is no way that that comment leads to any kind of copyright or encumbrance on the hash code algorithm used by DT_GNU_HASH.

Ian

[ali_e...@emvision.com]

On 8/11/22 11:26 AM, Cary Coutant wrote:
> The current discussion leading from Carlos' question about why DT_HASH
> is mandatory leads me to wonder why we shouldn't update the ELF
> standard with what is clearly a better hash algorithm. After all, we
> added support for the ZSTD compression algorithm.
>
> I would propose taking the current DT_GNU_HASH design pretty much as
> is and adding it to the ELF standard as DT_HASH_2. The GNU hash table
> imposes certain additional ordering requirements on the dynamic symbol
> table, but there is benefit in dynamic loader performance, I believe.
>
> At the same time, we would add DT_SYMTABSZ (or, equivalently,
> DT_SYMTAB_COUNT) to the dynamic table to make it possible to know the
> number of symbols without consulting the hash table.

That's a pretty big change. Sorry, but I vote against
requiring DT_GNU_HASH as a gABI feature. We don't want to be
required to support it.

I vote for adding DT_SYMTABSZ. I prefer this to DT_SYMTAB_COUNT
for various reasons that the gABI list won't be interested in
(symmetry with other ELFOSABI_SOLARIS DT definitions), but I
won't stand in the way of DT_SYMTAB_COUNT either.

My vote really isn't anti-GNU hash per se. I did a pretty deep
dive on it many years ago, as well as the cost of hashing
generally, and wrote a blog about it that has been preserved
here:

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

I also wrote about the costs of hashing generally, and while
I didn't explicitly say so then, our decision to not adopt
the GNU hash came out of that:

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

The GNU hash might be faster, but its also considerably more
complex. That's fine if you need it, but we find that using
direct bindings largely erases the advantage for us.

Please understand that the following is partly tongue in
cheek: If we're going to adopt better algorithms, then
perhaps direct bindings should also become part of the gABI?
The best way to speed up hashing is to do less of it.
I know that was flame bait, so please don't toast me. My
point here is that "better" has a lot to do with your context.
I am not seriously proposing that the gABI adopt direct bindings,
but I ask that we not be required to take GNU hash.

The difference between this and ZSTD is largely that we haven't
solved the problem ZSTD does in some other way. Also, the
SHF_COMPRESSED mechanism was designed from the start to support
adding algorithms.

I'd like to ask that my proposal from yesterday be considered
instead. Let's create the missing OSABI(s) for the platforms
that currently use GNU hash without declaring an OSABI.

- Ali

[Cary Coutant]

> That's a pretty big change. Sorry, but I vote against
> requiring DT_GNU_HASH as a gABI feature. We don't want to be
> required to support it.

There's a grey area between adding a new feature to the spec and
requiring all implementations to support it. Certainly no producer
would ever be compelled to use it, and a consumer would be obligated
only if it's part of a toolchain with producers that support it. And a
psABI could certainly require DT_HASH. (For example, we have TLS
support without requiring systems to support it.)

> I vote for adding DT_SYMTABSZ. I prefer this to DT_SYMTAB_COUNT
> for various reasons that the gABI list won't be interested in
> (symmetry with other ELFOSABI_SOLARIS DT definitions), but I
> won't stand in the way of DT_SYMTAB_COUNT either.

Yes, even without the new hash table, I would also support adding
DT_SYMTABSZ, which would enable making DT_HASH optional. I would
probably also opt for the SZ variant, simply because of the
established precedent with other DT entries, even though I think the
COUNT variant would really be more useful. I'm on the fence.

> Please understand that the following is partly tongue in
> cheek: If we're going to adopt better algorithms, then
> perhaps direct bindings should also become part of the gABI?
> The best way to speed up hashing is to do less of it.
> I know that was flame bait, so please don't toast me. My
> point here is that "better" has a lot to do with your context.
> I am not seriously proposing that the gABI adopt direct bindings,
> but I ask that we not be required to take GNU hash.

Not flame bait at all! I'd be very receptive to adding direct binding
to the gABI. I was pushing for a direct binding capability within HP a
long time ago, but could never overcome the pushback against it (not
even after you guys at Sun legitimized the idea!).

> The difference between this and ZSTD is largely that we haven't
> solved the problem ZSTD does in some other way. Also, the
> SHF_COMPRESSED mechanism was designed from the start to support
> adding algorithms.

Not sure I agree with your argument here. I think DT_GNU_HASH solves
the problems with DT_HASH in very much the same way that ZSTD solves
the problems with ZLIB. The difference is that SHF_COMPRESSED is a
flag in a limited namespace, and allocating a new flag for each new
compression algorithm would be unworkable as well as silly. Yes, we
could have designed DT_HASH to work that way, too, but. alas, we
didn't. With the virtually unlimited namespace for DT entries, though,
it's much more practical to allocate a new DT entry tag to accomplish
the same purpose. Perhaps (if we go ahead with this), the DT_HASH_2
table could be designed with extension in mind so we wouldn't need to
continue allocating new DT entry tags for new hash algorithms.

> I'd like to ask that my proposal from yesterday be considered
> instead. Let's create the missing OSABI(s) for the platforms
> that currently use GNU hash without declaring an OSABI.

I'll have to reflect on this some more. It's not clear to me that this
would really solve anything; on the contrary, it sounds like it'll
make things a bit more complex. DT_GNU_HASH is effectively a
quasi-standard value; its meaning can be understood without checking
the OSABI. Perhaps I should try to collect such "universal" or
"legacy" extensions in an appendix so that they can be documented and
protected from collision, without actively blessing them as part of
the standard.

-cary

[ali_e...@emvision.com]

On 8/12/22 4:12 PM, Cary Coutant wrote:
>> That's a pretty big change. Sorry, but I vote against
>> requiring DT_GNU_HASH as a gABI feature. We don't want to be
>> required to support it.
>
> There's a grey area between adding a new feature to the spec and
> requiring all implementations to support it. Certainly no producer
> would ever be compelled to use it, and a consumer would be obligated
> only if it's part of a toolchain with producers that support it. And a
> psABI could certainly require DT_HASH. (For example, we have TLS
> support without requiring systems to support it.)

Hi Cary,

I don't disagree with what you're saying. I don't think
that signing up for a standard necessarily means that one
signs up for 100% of it. I've had previous discussions here
though (not recently) where people felt the other way. I want
to be sure we all understand it the same way.

As an aside, that's one reason that I don't fully understand
the statement that these platforms using the GNU hash, but not
the other GNU stuff, can't set ELFOSABI_GNU in their objects. As
long as their objects fit within the GNU ABI envelope, why can't
they just support the subset they want, and still tag themselves
with that ABI? Perhaps they don't actually fit within that
envelope? I do understand of course, from earlier in the thread,
that this answer is not considered acceptable.

I think that putting things in the gABI does put a certain
sort of pressure on them. Perhaps systems aren't required to
support TLS, but the reality of FOSS that uses TLS makes it
a practical necessity. You don't have to support TLS in the
same sense that you don't have to have a working mail client
or web browser. :-) Of course, TLS is a bit different than
hash, because end programmers are aware of it. Hash is largely
just between the link-editor and the runtime linker. Perhaps
by dint of controlling both of those things on my platform,
I don't really have much to worry about. Let me ponder this
for a day or 2, and let's see if anyone else has an opinion.

> Not sure I agree with your argument here. I think DT_GNU_HASH solves
> the problems with DT_HASH in very much the same way that ZSTD solves
> the problems with ZLIB. The difference is that SHF_COMPRESSED is a
> flag in a limited namespace, and allocating a new flag for each new
> compression algorithm would be unworkable as well as silly. Yes, we
> could have designed DT_HASH to work that way, too, but. alas, we
> didn't. With the virtually unlimited namespace for DT entries, though,
> it's much more practical to allocate a new DT entry tag to accomplish
> the same purpose. Perhaps (if we go ahead with this), the DT_HASH_2
> table could be designed with extension in mind so we wouldn't need to
> continue allocating new DT entry tags for new hash algorithms.

True. Also, I'm not advocating for a "type" field in
the new hash section. New section types work just fine
for that.

My main argument was that I think ZSTD seems to solve a
problem that all platforms have, and there isn't a competing
solution in that space. That's not the same with GNU hash,
for my platform, though it probably is for others.

I don't think the ELF forefathers expected multiple hash
implementations to be a thing, evident in choices (nchain)
they made. In contrast, we weren't looking to encourage more
compression formats, but it was obviously coming, so we
took the extra steps to pave the way forward. As you point
out, this isn't a definitive argument in any sense.

>
>> I'd like to ask that my proposal from yesterday be considered
>> instead. Let's create the missing OSABI(s) for the platforms
>> that currently use GNU hash without declaring an OSABI.
>
> I'll have to reflect on this some more. It's not clear to me that this
> would really solve anything; on the contrary, it sounds like it'll
> make things a bit more complex. DT_GNU_HASH is effectively a
> quasi-standard value; its meaning can be understood without checking
> the OSABI. Perhaps I should try to collect such "universal" or
> "legacy" extensions in an appendix so that they can be documented and
> protected from collision, without actively blessing them as part of
> the standard.

I'm not sure I understand how tagging objects with an OSABI
is an added complexity. Isn't it more a case of using the
complexity we've already paid for? I think that any object that
used a value in the OSABI partition, even if it predates the gABI,
ought to declare an OSABI that covers it. I'd argue that this
is simpler than creating a new not-quite-gABI class, or at least,
not more complex.

Stiil, I can live with this other approach as well, and having it
protected, but not officially gABI, probably addresses any concerns
I might have had above. One minor complexity is that I presume that
ELF symbol versioning is in this class, and the GNU version of that
has some additions that the Sun versions don't have, and again, we
don't want to be forced into carrying them. But perhaps it's enough
to spell out the differences, and deal with it in the compilers,
as we already do.

Thanks.

- Ali

[Fangrui Song]

On 2022-08-12, Cary Coutant wrote:
>> That's a pretty big change. Sorry, but I vote against
>> requiring DT_GNU_HASH as a gABI feature. We don't want to be
>> required to support it.
>
>There's a grey area between adding a new feature to the spec and
>requiring all implementations to support it. Certainly no producer
>would ever be compelled to use it, and a consumer would be obligated
>only if it's part of a toolchain with producers that support it. And a
>psABI could certainly require DT_HASH. (For example, we have TLS
>support without requiring systems to support it.)

I wish we value a feature with its own merit and think about its
adoption, and not simply reject based on distaste.

As I see it, DT_HASH_2 (DT_GNU_HASH) remains optional. An OS is not
*required* to support it.

>> I vote for adding DT_SYMTABSZ. I prefer this to DT_SYMTAB_COUNT
>> for various reasons that the gABI list won't be interested in
>> (symmetry with other ELFOSABI_SOLARIS DT definitions), but I
>> won't stand in the way of DT_SYMTAB_COUNT either.
>
>Yes, even without the new hash table, I would also support adding
>DT_SYMTABSZ, which would enable making DT_HASH optional. I would
>probably also opt for the SZ variant, simply because of the
>established precedent with other DT entries, even though I think the
>COUNT variant would really be more useful. I'm on the fence.

Yes, I know the *SZ convention. This is a very loose convention to me.
In the meanwhile, we have DT_RELCOUNT/DT_RELACOUNT, perhaps from
Solaris, so *COUNT isn't entirely odd.

>> Please understand that the following is partly tongue in
>> cheek: If we're going to adopt better algorithms, then
>> perhaps direct bindings should also become part of the gABI?
>> The best way to speed up hashing is to do less of it.
>> I know that was flame bait, so please don't toast me. My
>> point here is that "better" has a lot to do with your context.
>> I am not seriously proposing that the gABI adopt direct bindings,
>> but I ask that we not be required to take GNU hash.
>
>Not flame bait at all! I'd be very receptive to adding direct binding
>to the gABI. I was pushing for a direct binding capability within HP a
>long time ago, but could never overcome the pushback against it (not
>even after you guys at Sun legitimized the idea!).

I agree that direct binding is great and generic ABI can add it. It
will solve the dynamic linking performance problem for glibc
https://sourceware.org/bugzilla/show_bug.cgi?id=16709
(I don't have a Solaris at hand, so I have very shallowing
understanding.)

Off-topic: I wish that the Linux world can make interposition opt-in instead of
opt-out
(https://maskray.me/blog/2021-05-16-elf-interposition-and-bsymbolic#the-last-alliance-of-elf-and-men)
(I have finally fixed all GNU ld x86-64 protected symbol regression since 2015-2016. There is now just
the GCC 5 HAVE_LD_PIE_COPYRELOC.)

* https://gitweb.dragonflybsd.org/dragonfly.git/commit/7629c6317998f850ebca23c296822ba08af09e5b (2012-03)
* https://cgit.freebsd.org/src/commit/?id=f62651920d526d8ef7a8ea66487e5bd1814a7a6f (2012-04)
* https://git.musl-libc.org/cgit/musl/commit/?id=2bd05a4fc26c297754f7ee5745a1c3b072a44b7d (2012-08)
* https://android.googlesource.com/platform/bionic/+/ec18ce06f2d007be40ad6f043058f5a4c7236573 (2014-11)
* https://github.com/openbsd/src/commit/ac51d06c6c4e6ed24fe575245f6450f3721e3842 (2018-11)
* https://github.com/NetBSD/src/commit/c01408307ce010883aac252f282645252f4c0a58 (2020-02)
* https://github.com/SerenityOS/serenity/commit/b370ee3423d9570f097adcbddcd07fac4285da52 (2021-01)

Marking an object ELFOSABI_GNU just to use a pretty "universal" feature
feels wrong to me. Nowaday many OSes use LLVM and a lot of features are
provided for all ELF based OSes (e.g. a dozen SHT_LLVM_* values). There
is little value in doing `if (osabi == linux/freebsd/netbsd/openbsd/etc)
display ...`, or adding host detection. The list is too long to
enumerate. There is little value in using ELFOSABI_GNU, defining
"ELFOSABI_GNUBASE" or "ELFOSABI_LLVM". In the meanwhile, taking a value
harms (mostly) nobody. AIUI these OSes using LLVM define value few ELF
values themselves (if any).

(Yes, I mainly care about Linux and *BSD, but I do review many changes
from Rainer Orth and him make Solaris better.)

So the potential conflict is, nowadays, mostly just between GNU/LLVM and
Solaris. I think knowing the values Solaris has taken and avoiding
using the ranges will work pretty well in practice.

>--
>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 view this discussion on the web visit https://groups.google.com/d/msgid/generic-abi/CAJimCsFpirMYtgwWFTf_0LmK2WrMuHkFPqRP-oN5cR%2BJuh2PFA%40mail.gmail.com.

[ali_e...@emvision.com]

On 8/12/22 5:34 PM, ali_e...@emvision.com wrote:
> Let me ponder this
> for a day or 2, and let's see if anyone else has an opinion.

I've taken a few days to think about this and to get
some clarity. I still don't want to see all of those early
GNU additions added to the generic ABI, even though it's
true that I could probably work around it if it happened.
I'd like to explain why.

The items in play here, primarily GNU hash, but also other
things such as symbol versioning, predate the creation of a
gABI, and of the OSABI partitioning that resulted. For that
reason, there seems to be some disagreement about what is
required for them in terms of setting an OSABI. Now that
OSABIs exist, do you have to set them for things that are
older than that?

There are items, such as DT_FLAGS_1, or DT_GNU_HASH, that
were really not generic, but which were added by various
implementations, rather than coming from Bell Labs with
the original ELF. These are extensions made before the gABI
happened. Folks would grab a value, hope that no one else had
grabbed the same one, and forge on. These things inevitably
started colliding, which eventually led to the gABI meetings
some 20 years ago that created the gABI, and OSABIs. There's
really no alternative to grandfathering in these items, and
doing our best to not step on each other's toes. No OSABI
applies.

There are other items, such as SHT_GNU_HASH (aka SHT_SUNW_SIGNATURE)
that also predate the gABI, but which today lie in OSABI territory,
and for which different OSABIs have assigned different meanings.
Even in cases (verdef, verneed, versym) where we all agree to
the basic meanings and have the same numeric values, the actual
semantics differ. We both have ancient claims to these values,
but the collision today is the point, rather than who was first.

That leaves GNU hash in the awkward position of being partially
grandfathered (DT_GNU_HASH) and partially, possibly, not
(SHT_GNU_HASH). Did no one notice this in 2002?

Even if I thought it made sense otherwise, I can't say yes to
this, because of the existing OSABI range collisions. 0x6ffffff6
can't be SHT_GNU_HASH on Solaris because it is already SHT_SUNW_SIGNATURE.
And so on for other examples, such as versioning. Were I to
implement GNU hash, I would have to assign the section a different
number. Names are are useful nmemonics, but the numeric values are
what makes an ABI, and some of these numbers are already taken.

For the OSABI concept to be useful, the only way I can see it
working, is that whenever an object uses values from an OSABI
range, the ELF header needs to declare an OSABI to establish
the namespace under which those values are interpreted. I think
this needs to be true whether or not the feature predates OSABIs,
because otherwise, the situation is ambiguous. I understand that
this isn't what's done today on some platforms, but I still haven't
heard a convincing explanation of why it shouldn't be.

- Why can't a GNU conforming platform set ELFOSABI_GNU even
if they don't implement IFUNC, or other post-gABI features?

- If there are reasons, then why shouldn't that platform be
expected to have their own OSABI, that includes the GNU
features they want to have? I'm sure there would be no
problem giving them an assignment, if they don't actually
already have one. It's no different than a machine assignment,
and no harder to acquire.

A different reply suggested that the whole world is now GNU,
and in not wanting these features in the gABI, I am forcing
an unreasonable inconvenience on everyone else. My main problem
with this is, to quote Monty Python, "We're not dead yet!". Not
only are we not dead, but we're certain to be around for at least
another decade (my opinion, you can make your own estimate). You
knew this club had other members when you joined it. :-)

In the meantime, the gABI is a shared space, and it's best if
we can figure out how to coexist. A month doesn't go by where I
don't think "Thank Goodness that GNU adopted ELF, and worked
for a gABI, rather than inventing some ELF-adjacent, but
incompatible, format of their own". Had they made that very
Microsoft-like move, the rest of us would be in a much worse
position today, probably with no compilers, and limited ability
to build open source software. There were benefits: A proven
solution, a community to share ideas and improve them,
the general benefits of wider communication. There are certainly
downsides as well: You have to make it work when things aren't
what you'd choose to do otherwise. You sometimes have to work
with folks you might otherwise ignore. Nonetheless, I think it's
been great. I've had a lot of help from folks in the GNU
community over the years, for which I am very grateful.

I don't want to inconvenience anyone, and I trust that over
the years, that's been apparent. But what is the nature of
the actual inconvenience? Is it really a big deal to set a
field in a header to a predefined number that identifies the
scope for that object?

eh.eh_ident[EI_OSABI] = ELFOSABI_you

And then, do whatever you want, within your scope
free and clear? This scheme is 20 years old, and GNU
were in that room when it was decided. Why was it agreed
to then, why is it a problem now, and what exactly is
the difficult part?

If the whole world is GNU, then all the objects will
be ELFOSABI_GNU. That's not a problem as far as I can see.
It doesn't stop you from doing anything you'd otherwise do.

Today, it might look like Solaris vs a 'pretty "universal"
feature', but any time you have more than one party, there will
eventually be a desire by one of them to do something
differently. You might all be aligned right now, but that
may not always be the case. As an old Unix guy, I often
note how the "Unix Wars" of the past have been replaced
by "Linux Distro Wars". There's nothing new under the sun.
We have a good mechanism in place for dealing with this --- I
say let's use it, and carry on.

Of course, the world isn't going to end if I trip over an
obviously GNU object that doesn't have its OSABI set. It
happens all the time. Still, it simplifies things if they do.

I don't think we really have a disagreement about the OSABI
notion itself, but perhaps it's time we clarified what's
expected around these preexisting, but not gABI, items, so that
we can put this issue to bed and not have to bring it up again.

It would also make sense to compile a list of those things,
as an addendum to the gABI, to make it easier for everyone
to identify them. However, these are by definition, anything
in the gABI partition that isn't in the gABI, so it's not
that hard to intuit.

To bring this long digression to a point:

- I think that objects that omit DT_HASH should
define an OSABI under which that omission makes
sense.

- I support adding a generic DT_ entry for specifying
the size of the .dynsym, to facilitate that.

- I don't think that the GNU hash needs to be part of
the gABI to justify dropping DT_HASH, or that moving it
to the gABI makes any difference to the ability of
various platforms to use it. The gABI isn't better
or worse than an OSABI. It's just a different, shared,
namespace.

Thanks for listening.

- Ali

[ali_e...@emvision.com]

On 8/12/22 5:36 PM, 'Fangrui Song' via Generic System V Application Binary Interface wrote:
> (Yes, I mainly care about Linux and *BSD, but I do review many changes
> from Rainer Orth and him make Solaris better.)

I would like to publicly acknowledge that this is
true, and that we greatly appreciate it. LLVM has put new
strains our our plumbing, and we probably couldn't make it
work without the help, and ability to participate and get
patches in. LLVM use is growing in our world, and we're
happy to not be left out.

I hope that you've felt some mutual benefit in return,
but in any event, we thank you, and look forward to
lots more.

- Ali