RFC: ELF: Deduplicate strings without a null terminator

[Trevor Gross]

Hi all,

Is there any appetite for providing linkers a way to merge binary
sequences that are not null-terminated?

Data marked SHF_STRINGS with SHF_MERGE can be combined based on suffix
matching, which LLD does with -O2 [1], but SHF_STRINGS requires a
trailing '\0'. For C/++ this is usually fine since string literals can
always be combined, only static arrays can't. However, this is more of
a problem for languages such as Rust and Go that do not use
null-terminated strings by default, and so can't benefit from these
optimizations [^1].

If a linker were aware of sequences without terminators then it could
pretty easily perform trivial deduplication, possibly also the same
suffix-based merging that it does to null-terminated strings. In
theory it would also be possible to compress further than for
SHF_STRINGS, such as with a prefix matching pass or a full
arbitrary-position substring matcher (with link time tradeoffs, of
course).

Implementation-wise the ELF format would need to gain some form of
lengths table, either via a PROGBITS flag indicating the section
contains a discardable header, or with a new section type [^2].

Curious to hear what everyone thinks, or if this has been considered
before and I just couldn't find it.

Cheers,
Trevor

[1]: https://man.archlinux.org/man/extra/lld/ld.lld.1.en

[^1]: In these cases it is possible to add a '\0' as long as the
string does not already contain one, but this comes with the downside
of increased binary size in cases where merging doesn't help.
[^2]: Always splitting strings to separate SHF_MERGE .rodata.*
sections may work as well, but this seems more likely to interfere
with existing compiler section-splitting logic and doesn't allow
merging to happen more than once.

(Copying Andrew and Sam since I discussed this a bit with them on IRC)