Details

Reviewers

kib
fbsd-phab_maskray.me

Commits

rG9e4ae81971f7: link_elf: fix SysV hash function overflow
rG26cc23c84e0e: rtld: fix SysV hash function overflow
rG2ef2c26f3f13: link_elf: fix SysV hash function overflow
rG29e3a0651082: rtld: fix SysV hash function overflow

Summary

Quoting from https://maskray.me/blog/2023-04-12-elf-hash-function:

The System V Application Binary Interface (generic ABI) specifies the
ELF object file format. When producing an output executable or shared
object needing a dynamic symbol table (.dynsym), a linker generates a
.hash section with type SHT_HASH to hold a symbol hash table. A DT_HASH
tag is produced to hold the address of .hash.

The function is supposed to return a value no larger than 0x0fffffff.
Unfortunately, there is a bug. When unsigned long consists of more than
32 bits, the return value may be larger than UINT32_MAX. For instance,
elf_hash((const unsigned char *)"\xff\x0f\x0f\x0f\x0f\x0f\x12") returns
0x100000002, which is clearly unintended, as the function should behave
the same way regardless of whether long represents a 32-bit integer or
a 64-bit integer.

Sponsored by:   The FreeBSD Foundation

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

emaste requested review of this revision.Apr 12 2023, 2:10 PM

emaste created this revision.

I read that thread. Wouldn't it be better/cleaner to change types to uint32_t, or even Elf32_Word?

sys/kern/link_elf.c
1479–1480	g is unused now?

Use 0x0fffffff to make it more obvious that this is 28 bits not 32.

Incorporate kib feedback

Still do not want to use Elf32Word?

BTW, what about re-indenting the function as the preparatory commit? You change more lines than keep intact.

sys/kern/link_elf.c
1474	The last sentence from the comment is worth keeping as well, IMO.
1479	I mean, the h var type should be changed as well.

More kib feedback
Reindent first (this diff is against the reindent, which will be committed independently first)
edit libexec/rtld-elf/rtld.c instead of sys/kern/link_elf.c

Presumably we should make the same change in rtld.c and link_elf.c

Herald added a subscriber: bdragon. · View Herald TranscriptApr 12 2023, 3:17 PM

kib added inline comments.Apr 12 2023, 3:25 PM

libexec/rtld-elf/rtld.c
1805 ↗	(On Diff #120196)
sys/kern/link_elf.c
1478
1479–1480

Include both rtld and kernel.
I'd expect this to be three separate commits:

reindent rtld
rtld
kernel

libexec/rtld-elf/rtld.c
1805 ↗	(On Diff #120196)	will include with the reindent commit

style(9) fixup from kib

kib accepted this revision.Apr 12 2023, 3:45 PM

This revision is now accepted and ready to land.Apr 12 2023, 3:45 PM

LGTM. I made a post last night and did plan to make this FreeBSD change for my exercise, but you beat it to me :)

fbsd-phab_maskray.me added a comment.Apr 12 2023, 4:42 PM

This comment was removed by fbsd-phab_maskray.me.

elf_hash((const unsigned char *)"ZZZZZW9p")) == 100000000. This is an all-ascii-alphanumeric identifier.
For extra fun, you may try ld -shared --hash-style=sysv and ensure 100000000 % nbucket != 0 (lld sets nbucket to the number of dynamic symbols) and see whether the dynamic symbol cannot be bound without this patch:)

Closed by commit rG29e3a0651082: rtld: fix SysV hash function overflow (authored by emaste). · Explain WhyApr 12 2023, 4:49 PM

This revision was automatically updated to reflect the committed changes.

emaste mentioned this in rG87443cb6c669: rtld: reindent and style(9) elf_hash().

emaste added a commit: rG29e3a0651082: rtld: fix SysV hash function overflow.

Herald added a subscriber: imp. · View Herald TranscriptApr 12 2023, 4:49 PM

For extra fun, you may try ld -shared --hash-style=sysv and ensure 100000000 % nbucket != 0 (lld sets nbucket to the number of dynamic symbols) and see whether the dynamic symbol cannot be bound without this patch:)

Indeed, I made a test object with two functions

void ZZZZZW9p(void) { }
void fn(void) { }

which gives 3 dynamic symbols.

SysV hash section:

Hex dump of section '.hash':
  0x00000210 03000000 03000000 01000000 00000000 ................
  0x00000220 02000000 00000000 00000000 00000000 ................

When linked with --hash-style=sysv, dlsym(dl, "ZZZZZW9p") returns null (i.e., fails). When linked wtih --hash-style=gnu it works. With this patch (D39517) applied to rtld it works for both hash styles.

In D39517#900001, @emaste wrote:
For extra fun, you may try ld -shared --hash-style=sysv and ensure 100000000 % nbucket != 0 (lld sets nbucket to the number of dynamic symbols) and see whether the dynamic symbol cannot be bound without this patch:)

Indeed, I made a test object with two functions
void ZZZZZW9p(void) { }
void fn(void) { }
which gives 3 dynamic symbols.

SysV hash section:
Hex dump of section '.hash':
  0x00000210 03000000 03000000 01000000 00000000 ................
  0x00000220 02000000 00000000 00000000 00000000 ................
When linked with --hash-style=sysv, dlsym(dl, "ZZZZZW9p") returns null (i.e., fails). When linked wtih --hash-style=gnu it works. With this patch (D39517) applied to rtld it works for both hash styles.

Did you tried linking the dso with ld.bfd?

it looks like bfd sets nbuckets=1 for my test object so isn't useful to create the problem.

Hex dump of section '.hash':
  0x00000120 01000000 03000000 02000000 00000000 ................
  0x00000130 00000000 01000000                   ........

but bfd added & 0xffffffff decades ago as mentioned in the blog - https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=32dfa85d9015feea4a06d423fe58f6eaf841456e

emaste added a commit: rG2ef2c26f3f13: link_elf: fix SysV hash function overflow.Apr 12 2023, 7:34 PM

emaste mentioned this in rG937d152b3e62: rtld: reindent and style(9) elf_hash().Apr 27 2023, 6:20 PM

emaste added a commit: rG26cc23c84e0e: rtld: fix SysV hash function overflow.

emaste added a commit: rG9e4ae81971f7: link_elf: fix SysV hash function overflow.