UBSan complains about map::__find_equal_key (invalid upcast)

[Quuxplusone]

Bugzilla Link	PR31402
Status	RESOLVED FIXED
Importance	P normal
Reported by	Vedant Kumar (vsk@apple.com)
Reported on	2016-12-15 19:01:07 -0800
Last modified on	2017-01-05 00:15:55 -0800
Version	unspecified
Hardware	PC All
CC	dexonsmith@apple.com, eric@efcs.ca, llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

UBSan complains about an invalid upcast in map::__find_equal_key. Here are the
steps I took to reproduce this issue:

1) Check out an ToT llvm and libcxx.

2) Revert r264989 from the libcxx checkout. That's:

"Fix LWG issue 2469 - Use piecewise construction in map::operator[]."

3) Configure llvm with this cmake command:

cmake -G Ninja \
    -DLLVM_TARGETS_TO_BUILD="X86;ARM;AArch64" \
    -DCMAKE_BUILD_TYPE:STRING=Release \
    -DLLVM_ENABLE_ASSERTIONS:BOOL=On \
    -DLLVM_USE_SANITIZER=Undefined \
    ..

It's important to use "Release". This is an -fsanitize=object-size violation,
so we need optimizations on to trigger it.

4) Make sure we're building with our libcxx checkout. E.g:

$ export CCC_OVERRIDE_OPTIONS="+-I/Users/vk/Desktop/llvm/projects/libcxx"

The QA override is a convenient way to do this.

5) Build the lib/Target/ARM/ARMGenAsmMatcher.inc target. E.g:

$ ninja -v lib/Target/ARM/ARMGenAsmMatcher.inc

6) I then get:

FAILED: lib/Target/ARM/ARMGenAsmMatcher.inc.tmp
cd /Users/vk/Desktop/llvm/ubsan-R/lib/Target/ARM &&
/Users/vk/Desktop/llvm/ubsan-R/bin/llvm-tblgen -gen-asm-matcher -I
/Users/vk/Desktop/llvm/lib/Target/ARM -I /Users/vk/Desktop/llvm/include -I
/Users/vk/Desktop/llvm/lib/Target /Users/vk/Desktop/llvm/lib/Target/ARM/ARM.td -
o /Users/vk/Desktop/llvm/ubsan-R/lib/Target/ARM/ARMGenAsmMatcher.inc.tmp
/Users/vk/Desktop/llvm/projects/libcxx/include/map:1382:16: runtime error:
downcast of address 0x7fff5c878208 with insufficient space for an object of
type 'std::__1::__tree_node_base<void *>'
0x7fff5c878208: note: pointer points here
 ff 7f 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  05 01 73 65 72 73 2f 76  74 bd 64 03
              ^
0  llvm-tblgen              0x000000010354dff6 llvm::sys::RunSignalHandlers() +
118
1  llvm-tblgen              0x000000010354f6e1 SignalHandler(int) + 321
2  libsystem_platform.dylib 0x00007fffb6d2cfba _sigtramp + 26
Stack dump:
0.      Program arguments: /Users/vk/Desktop/llvm/ubsan-R/bin/llvm-tblgen -gen-
asm-matcher -I /Users/vk/Desktop/llvm/lib/Target/ARM -I
/Users/vk/Desktop/llvm/include -I /Users/vk/Desktop/llvm/lib/Target
/Users/vk/Desktop/llvm/lib/Target/ARM/ARM.td -o /Users/vk/Desktop/llvm/ubsan-
R/lib/Target/ARM/ARMGenAsmMatcher.inc.tmp
/bin/sh: line 1: 59222 Abort trap: 6           /Users/vk/Desktop/llvm/ubsan-
R/bin/llvm-tblgen -gen-asm-matcher -I /Users/vk/Desktop/llvm/lib/Target/ARM -I
/Users/vk/Desktop/llvm/include -I /Users/vk/Desktop/llvm/lib/Target
/Users/vk/Desktop/llvm/lib/Target/ARM/ARM.td -o /Users/vk/Desktop/llvm/ubsan-
R/lib/Target/ARM/ARMGenAsmMatcher.inc.tmp
ninja: build stopped: subcommand failed.

I believe the issue is masked on our bots by r264989 because we stop calling
__find_equal_key as often.

[Quuxplusone]

Step 4 is wrong, the override should be:

export CCC_OVERRIDE_OPTIONS="+-I/Users/vk/Desktop/llvm/projects/libcxx/include"

[Quuxplusone]

Why are you reverting r264989?

[Quuxplusone]

Thoughts so far:

1. I can reproduce following the steps provided on Linux w/ ToT Clang.

2. I agree there is still a bug in __find_equal_key. Perhaps not in the downcast but in the subsequent dereference. I think I know how to fix it.

3. I haven't managed to write a reproducer small enough for the test suite. I have no idea why UBSAN sees the object size violation in that case but not in others. I know there are tests which exercise the offending line of code. Maybe the UBSAN flags used by the test suite are wrong?

[Quuxplusone]

Fix up for review as https://reviews.llvm.org/D28131.

Still can't write a test case though :-(

[Quuxplusone]

Why are you reverting r264989?

I originally saw this failure on an internal UBSan bot. The bot used to build with a version of libcxx which hadn't picked up r264989. Once I applied r264989 I saw that the issue was masked.

I haven't reduced the problem beyond the tablegen invocation I listed.

[Quuxplusone]

Fixed in r291087 (4.0)