Undefined behavior in __tree

[llvmbot]

Bugzilla Link	19302
Resolution	FIXED
Resolved on	Dec 14, 2016 16:04
Version	unspecified
OS	Linux
Blocks	#21189 #28974
Reporter	LLVM Bugzilla Contributor
CC	@andreyv,@bbannier,@bcardosolopes,@Dushistov,@gnzlbg,@arsenm,@mclow,@zygoloid,@seanm

Extended Description

While debugging a gold linker issue I came across the following
-fsanitize=undefined runtime error:

/usr/include/c++/v1/list:218:19: runtime error: downcast of address 0x7fffa93b8e88 with insufficient space for an object of type 'std::__1::__list_node<gold::Output_section::
Input_section, void *>'
0x7fffa93b8e88: note: pointer points here
00 00 00 00 50 94 3b a9 ff 7f 00 00 20 3b d1 02 00 00 00 00 00 00 00 81 ff ff ff ff 01 00 00 00
^
/usr/include/c++/v1/list:219:19: runtime error: downcast of address 0x7fffa93b8e88 with insufficient space for an object of type 'std::__1::__list_node<gold::Output_section::
Input_section, void *>'
0x7fffa93b8e88: note: pointer points here
00 00 00 00 88 8e 3b a9 ff 7f 00 00 20 3b d1 02 00 00 00 00 00 00 00 81 ff ff ff ff 01 00 00 00
^
/usr/include/c++/v1/list:592:25: runtime error: downcast of address 0x7fffa93b8ed0 with insufficient space for an object of type 'std::__1::__list_node<gold::Output_section::Input_section, void *>'
0x7fffa93b8ed0: note: pointer points here
ff 7f 00 00 30 2e 04 03 00 00 00 00 30 2e 04 03 00 00 00 00 01 00 00 00 00 00 00 00 70 89 65 03
^
/usr/include/c++/v1/__tree:834:16: runtime error: downcast of address 0x7fffa93b8e00 with insufficient space for an object of type 'std::__1::__tree_node<std::__1::__value_type<std::__1::basic_string<char, std::__1::char_traits, std::__1::allocator >, gold::Output_segment *>, void *>'
0x7fffa93b8e00: note: pointer points here
00 00 00 00 40 21 0a 03 00 00 00 00 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

See: http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031213.html
for an analysis of the issue by Richard Smith.

Basically one should use use reinterpret_cast instead of static_cast to
avoid the undefined behavior.

[mclow]

This looks very similar to http://llvm.org/bugs/show_bug.cgi?id=18488.

(Not saying it's a duplicate, but they're related)

[arsenm]

Use reinterpret_cast
Using reinterpret_cast seems to work, and allows me to complete compiling LLVM with ubsan

[llvmbot]

Hi Matt, Unfortunately your patch does not work with "fancy" pointers (class types that act like pointers). Instead it causes a compile error since you cant reinterpret_cast the class type. I'll continue looking into the issue.

[arsenm]

Hi Matt, Unfortunately your patch does not work with "fancy" pointers (class
types that act like pointers). Instead it causes a compile error since you
cant reinterpret_cast the class type. I'll continue looking into the issue.

Any chance of fixing this before the release?

[llvmbot]

I can try and dedicate monday to it but I make no promises.

[llvmbot]

I've bumped into this while trying to setup UBSan bootstrap of LLVM with -stdlib=libc++:

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/5521/steps/build%20clang%2Fubsan/logs/stdio
If
This error makes libc++ pretty much unusable with UBSan. And, again, the 3.6 release is coming :(

If reinterpret_cast isn't working, our options seem to be pretty limited. E.g. we can make __tree::__end_node() return __end_node_ptr, and add some tricks to allow assigning __end_node_ptr to __node_pointer, and to initialize tree iterator with __end_node_ptr ( I haven't tried implementing it, though ).

[llvmbot]

We also have a libc++/libc++abi UBSAN bot that can be found here:

http://lab.llvm.org:8011/builders/libcxx-libcxxabi-x86_64-linux-ubuntu-ubsan/builds/95

A fair amount of the failures are caused by a single pointer cast in libc++abi,
but there are also failures caused by undefined behavior in
std::forward_list,
std::list,
and std::__tree.

I'm going to try and tackle std::list first.

[llvmbot]

Possible fix up for review as D6974

http://reviews.llvm.org/D6974

[gnzlbg]

I'm getting similar issues in __tree (trunk) but at slightly different lines

/home/gonzalo/pool/include/c++/v1/__tree:836:16: runtime error: downcast of misaligned address 0x7fffffffb008 for type 'std::__1::__tree_node<std::__1::__value_type<fmt::BasicStringRef, fmt::internal::Arg>, void *>', which requires 16 byte alignment
0x7fffffffb008: note: pointer points here
a0 61 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 e0 b4 ff ff ff 7f 00 00 e0 b1 ff ff
^
SUMMARY: AddressSanitizer: undefined-behavior /home/gonzalo/pool/include/c++/v1/__tree:836:16 in
/home/gonzalo/pool/include/c++/v1/__tree:877:51: runtime error: upcast of misaligned address 0x7fffffffb008 for type 'std::__1::__tree_node<std::__1::__value_type<fmt::BasicStringRef, fmt::internal::Arg>, void *>', which requires 16 byte alignment
0x7fffffffb008: note: pointer points here
ff 7f 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 e0 b4 ff ff ff 7f 00 00 e0 b1 ff ff
^
SUMMARY: AddressSanitizer: undefined-behavior /home/gonzalo/pool/include/c++/v1/__tree:877:51 in
/home/gonzalo/pool/include/c++/v1/__tree:877:65: runtime error: load of misaligned address 0x7fffffffb008 for type 'pointer' (aka 'std::__1::__tree_node_base<void *> *'), which requires 16 byte alignment
0x7fffffffb008: note: pointer points here
ff 7f 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 e0 b4 ff ff ff 7f 00 00 e0 b1 ff ff

[llvmbot]

Fixed in list in r256652.
Fixed in forward_list in r258888.

Only __tree is left.

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#22871 has been marked as a duplicate of this bug. ***

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#28469 has been marked as a duplicate of this bug. ***

[llvmbot]

Committed to trunk in r276003. I'll close this once it's merged into 3.9.

After that I'll open a separate bug to track the UB in __hash_table.

[llvmbot]

Merged into 3.9 in r276212.

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#31376 has been marked as a duplicate of this bug. ***

[llvmbot]

mentioned in issue #21189

[llvmbot]

mentioned in issue llvm/llvm-bugzilla-archive#22871

[llvmbot]

mentioned in issue llvm/llvm-bugzilla-archive#28469

[zmodem]

mentioned in issue #28974

[llvmbot]

mentioned in issue llvm/llvm-bugzilla-archive#31376