LLD crashes on Rust generated code with ASan/libfuzzer

[m-gupta]

Bugzilla Link	43147
Resolution	FIXED
Resolved on	Jan 26, 2020 13:21
Version	unspecified
OS	Linux
Blocks	#43900
CC	@MaskRay,@kcc,@LebedevRI,@lalozano,@m-gupta,@morehouse,@pcc,@rui314,@smithp35

Extended Description

We are building fuzzers for rust code in Chrome OS.

When switching to lld for linking, lld crashes when linking rust fuzzers.

Reproducer:
https://drive.google.com/drive/folders/1hX7MHQGIocdCx2oraKqSbCohXYs8QAbS?usp=sharing

ld.lld @​response.txt
Stack dump:
0. Program arguments: ../bin/ld.lld @​response.txt

#​0 0x00005631e7cf2390 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/llvm/lib/Support/Unix/Signals.inc:533:22
#​1 0x00005631e7cf2423 PrintStackTraceSignalHandler(void*) /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/llvm/lib/Support/Unix/Signals.inc:594:1
#​2 0x00005631e7cf05bd llvm::sys::RunSignalHandlers() /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/llvm/lib/Support/Signals.cpp:68:20
#​3 0x00005631e7cf1e0c SignalHandler(int) /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/llvm/lib/Support/Unix/Signals.inc:385:1
#​4 0x00007f08bec233a0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x123a0)
#​5 0x00005631e7fbc6f2 compareByFilePosition(lld::elf::InputSection*, lld::elf::InputSection*) /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/lld/ELF/Writer.cpp:1530:18
#​6 0x00005631e800911a bool __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)>::operator()<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > > >(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >) /usr/include/c++/8/bits/predefined_ops.h:143:49
#​7 0x00005631e8009032 void std::__insertion_sort<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)> >(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)>) /usr/include/c++/8/bits/stl_algo.h:1847:4
#​8 0x00005631e800a461 void std::__chunk_insertion_sort<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, long, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)> >(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, long, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)>) /usr/include/c++/8/bits/stl_algo.h:2696:12
#​9 0x00005631e80093c7 void std::__merge_sort_with_buffer<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, lld::elf::InputSection**, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)> >(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, lld::elf::InputSection**, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)>) /usr/include/c++/8/bits/stl_algo.h:2718:26
#​10 0x00005631e8007c63 void std::__stable_sort_adaptive<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, lld::elf::InputSection**, long, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)> >(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, lld::elf::InputSection**, long, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)>) /usr/include/c++/8/bits/stl_algo.h:2753:25
#​11 0x00005631e8005bf5 void std::__stable_sort<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)> >(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__ops::_Iter_comp_iter<bool ()(lld::elf::InputSection, lld::elf::InputSection*)>) /usr/include/c++/8/bits/stl_algo.h:5001:15
#​12 0x00005631e8000069 void std::stable_sort<__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, bool ()(lld::elf::InputSection, lld::elf::InputSection*)>(__gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, __gnu_cxx::__normal_iterator<lld::elf::InputSection**, std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* > >, bool ()(lld::elf::InputSection, lld::elf::InputSection*)) /usr/include/c++/8/bits/stl_algo.h:5077:5
#​13 0x00005631e7ff91fe void llvm::stable_sort<std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* >&, bool ()(lld::elf::InputSection, lld::elf::InputSection*)>(std::vector<lld::elf::InputSection*, std::allocatorlld::elf::InputSection* >&, bool ()(lld::elf::InputSection, lld::elf::InputSection*)) /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/llvm/include/llvm/ADT/STLExtras.h:1323:1
#​14 0x00005631e7fdd583 (anonymous namespace)::Writer<llvm::object::ELFType<(llvm::support::endianness)1, true> >::resolveShfLinkOrder() /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/lld/ELF/Writer.cpp:1560:14
#​15 0x00005631e7fce0f2 (anonymous namespace)::Writer<llvm::object::ELFType<(llvm::support::endianness)1, true> >::finalizeSections() /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/lld/ELF/Writer.cpp:1930:3
#​16 0x00005631e7fbf59c (anonymous namespace)::Writer<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run() /usr/local/google/home/manojgupta/llvm_monorepo/llvm-project/lld/ELF/Writer.cpp:581:3

[smithp35]

Just taking a quick look before going home for the Evening. It looks like the crash is caused by a __sancov_pcs InputSection not being assigned to an OutputSection this causes writer.cpp::compareByFilePosition() to access a nullptr.

This looks to be triggered by garbage collection. Whereupon a __sancov_cntrs section is live but the InputSection it has a link order dependency on is not.

strictly speaking ELF permits this, and LLD shouldn't crash; however I think it will be worth checking with the sanitizer folk that this situation is expected as SHF_LINK_ORDER usually implies a 1:1 relationship with the dependent section.

The sections come from build/amd64-generic/tmp/portage/dev-rust/p9-0.1.0-r13/work/x86_64-cros-linux-gnu/release/deps/p9_tframe_decode_fuzzer-ab429f979ef544a2.p9_tframe_decode_fuzzer.czbue7pe-cgu.1.rcgu.o

These are:
Section #​804 .text._ZN3std2io5error5Error3new17hfea99a629fa675e7E

Section #​4289 __sancov_cntrs with link order dependency on Section #​804 .text._ZN3std2io5error5Error3new17hfea99a629fa675e7E

I've not traced through garbage collection, just a quick look in the object.

There are relocations from multiple .text.* sections to Section #​4289 which I guess at least one of these is causing it be live. There are relocations to Section #​804 but I guess these sections may not be live.

Do you happen to know if multiple sections are supposed to have relocations to a single __sancov_cntrs or is it expected that only the section that the __sancov_cntrs has a SHF_LINK_ORDER dependency on can have relocations to the __sancov_cntrs?

If it is expected that multiple .text.* Sections can have relocations to a single __sancov_cntrs then we'll have to alter LLD so that if the __sancov_cntrs section is live then it makes the SHF_LINK_ORDER section live as well.

[m-gupta]

+Kostya for sanitize coverage related questions.

[m-gupta]

+Matt morehouse for sanitizer coverage questions since Kostya is currently out.

[MaskRay]

The weird thing is:

% readelf -Wr build/amd64-generic/tmp/portage/dev-rust/p9-0.1.0-r13/work/x86_64-cros-linux-gnu/release/deps/p9_tframe_decode_fuzzer-ab429f979ef544a2.p9_tframe_decode_fuzzer.czbue7pe-cgu.1.rcgu.o
...
Relocation section '.rela.text.ZN3std2io16append_to_string28$u7b$$u7b$closure$u7d$$u7d$17h1f0dc57770ef30daE' at offset 0x3f9400 contains 23 entries:
...
00000000000000ee 00000fe600000002 R_X86_64_PC32 0000000000000000 __sancov_cntrs - 5

This relocation keeps #​4289 __sancov_cntrs live, however,
#​4289's sh_link #​804 is garbage-collected. This can cause null pointer dereferences in
(1) Writer.cpp:compareByFilePosition
(2) OutputSection::finalize()

This raises a question:
if st_link(A)=B, A has a link order dependency on B (it usually(exploited by sanitizers) means A is a metadata section of B),
and A is retained, should B be retained as well?

The converse is agreed by multiple parties: if B is retained, A should be retained as well.
See the suggested wording on
https://groups.google.com/forum/#!searchin/generic-abi/LINK_ORDER%7Csort:date/generic-abi/_CbBM6T6WeM/pf_kDY3XCwAJ

the link editor should ensure that both the section and the referenced section are retained or discarded together

I see the argument that A being retained implies B being retained,
but don't see the argument that B being retained implies A being retained.

[MaskRay]

A reproduce:

.globl _start
_start:
call foo

.section .bar,"a",@progbits
nop

.section .foo,"ao",@progbits,.bar # "o" is a llvm-mc specific syntax that is not supported by GNU as
.globl foo
foo:
nop

Currently none of ld.bfd/gold/lld uses sh_link as evidence that the linked section should be retained.

lld: if I patch out the two null pointer dereferences, .foo is kept, .bar is discarded
gold: .foo is kept, .bar is discarded
ld.bfd: ld.bfd: a: sh_link of section .foo' points to discarded section .bar' of `a.o'

[smithp35]

I think that one of the motivations behind SHF_LINK_ORDER is to build up an auxiliary table of metadata in the same order as the sections that they described. This is certainly the case with .ARM.exidx.

What does it mean for order if the metadata section is live but the section the metadata is relying on to get the right order has been removed?

Possible options:
1.) keep the metadata and the section it has a sh_link to.
2.) keep the metadata only but place it last after all other SHF_LINK_ORDER sections.

I'm not sure what use the sanitizer run time makes of the order of the __sancov_ctr sections. If it does not then it probably doesn't matter which we choose to do. If it does then we'll need to be mindful of it.

I'm a little bit suspicious of the object files, I'd have expected that like the .ARM.exidx design, no other section can make the metadata section live other than via the sh_link section being live.

[m-gupta]

Hi Peter and Fang-Rui,

Can we agree on a solution for this? We have switched to LLD in Chrome OS but Rust packages are still using Gold linker because of this crash.

[smithp35]

Looking at gold it looks like it doesn't implement SHF_LINK_ORDER apart from a special case for Arm exception index table sections SHT_ARM_EXIDX. In layout.cc // FIXME: Handle SHF_LINK_ORDER somewhere.

This implies that we shouldn't look to gold for guidance on what to do here, and if the sanitizers have been actually relying on SHF_LINK_ORDER then they ought not to be using gold.

Looking at ld.bfd there is an error message given when this case occurs bfd/elf.c assign_section_numbers():

ld.bfd: lobfd.exe: sh_link of section foo' points to discarded section .baz' of `lo.o'
ld.bfd: final link failed: Bad value

I got this via extending Fangrui's example to show that gold does not do SHF_LINK_ORDER processing, and ld.bfd errors when --gc-sections is on. LLD crashes as per the PR.

ENTRY(_start)
SECTIONS {
bar : { *(.bar) *(.baz) }
foo : { *(.foo.1) *(.foo.2) }
}

.globl _start
_start:
call bar
call foo2

.section .bar,"ax",@progbits
bar:
call foo1

.section .baz,"ax",@progbits
baz:
call foo2

.section .foo.1,"axo",@progbits,.baz # "o" is a llvm-mc specific syntax that is not supported by GNU as
.globl foo1
foo1:
nop

.section .foo.2,"axo",@progbits,.bar # "o" is a llvm-mc specific syntax that is not supported by GNU as
.globl foo2
foo2:
nop

I personally think that ld.bfd has the right idea here and LLD should give an error message rather than crashing. The program is not well defined under garbage collection. It may be for the sanitizers, this makes no difference, but there could be other programs that would end up with a runtime error if the linker arbitrarily decided to work around it by either keeping the section that would otherwise be discarded, or by removing the SHF_LINK_ORDER dependency if the linked section was not live.

I think that linking with gold has just avoided the problem because it doesn't implement SHF_LINK_ORDER. A better work around for LLD is to disable garbage collection.

[morehouse]

I wouldn't expect SanCov counters to have any references except from the function they have a sh_link dependency on. I am curious how this is happening.

Some background in case it helps understand what SanCov is doing:

We started adding associated metadata to the sancov_pcs arrays to prevent them from getting garbage collected by some linkers when the function they referenced was still live (#34636 ). I'm pretty sure this is where the sh_link dependency comes from.

The sancov_cntrs arrays didn't seem to need the associated metadata since they were already being referenced from the code by inline increments (++). However, we need the sancov_pcs and sancov_cntrs sections to have the same ordering since libFuzzer looks up the PC associated with a counter by looking up the sancov_cntrs offset in sancov_pcs. So we ended up adding associated metadata to sancov_cntrs as well to maintain the same ordering.

[MaskRay]

The crash has been fixed on lld's side for a while

ld.lld: error: build/amd64-generic/tmp/portage/dev-rust/p9-0.1.0-r13/work/x86_64-cros-linux-gnu/release/deps/p9_tframe_decode_fuzzer-ab429f979ef544a2.
p9_tframe_decode_fuzzer.czbue7pe-cgu.1.rcgu.o:(__sancov_cntrs): sh_link points to discarded section build/amd64-generic/tmp/portage/dev-rust/p9-0.1.0-
r13/work/x86_64-cros-linux-gnu/release/deps/p9_tframe_decode_fuzzer-ab429f979ef544a2.p9_tframe_decode_fuzzer.czbue7pe-cgu.1.rcgu.o:(.text._ZN3std2io5e
rror5Error3new17hfea99a629fa675e7E)

I think it is correct for lld to reject such a case.

For my reading of https://reviews.llvm.org/D29104 and https://reviews.llvm.org/D29110, there are some unclear semantics about the metadata !associated. A metadata does not appear to be the most appropriate construct to represent such a relation. In particular, optimizations can usually feel free to drop metadata they don't understand, but !associated exposes some restrictions. Some developers feel that at least for some metadata, optimizations should retain them, but this has not reached consensus. https://reviews.llvm.org/D72899

[zmodem]

mentioned in issue #43900