[llvm-bugs] [Bug 42065] New: Use after free (in DenseMap) in InstCombine when built with GCC

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=42065

            Bug ID: 42065
           Summary: Use after free (in DenseMap) in InstCombine when built
                    with GCC
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Support Libraries
          Assignee: unassignedbugs at nondot.org
          Reporter: martin at martin.st
                CC: llvm-bugs at lists.llvm.org

Created attachment 22048
  --> https://bugs.llvm.org/attachment.cgi?id=22048&action=edit
Small testcase

InstCombine contains the following construct:

DenseMap<Value *, Value *> NewInsts;
...
NewInsts[CI] = NewInsts[CI->getOperand(0)];

When built with GCC, this can trigger use after free. First the right hand side
is evaluated by calling operator[], which returns a reference. Then the left
hand side is evaluated, which also calls operator[], which triggers a call to
grow(), which reallocates the DenseMap, invalidating the right hand side
reference. After both sides have been evaluated, the right hand side reference
is dereferenced, which now points to freed memory.

When built with Clang, this isn't an issue because the reference is
dereferenced before evaluating the left hand side.

A small testcase that can illustrate the issue is attached. If built with GCC
with address sanitizer, running the testcase ends up with the following
backtrace:

==30663==ERROR: AddressSanitizer: heap-use-after-free on address 0x6190000000f8
at pc 0x5624235f0ccc bp 0x7ffc8e824b40 sp 0x7ffc8e824b30
READ of size 8 at 0x6190000000f8 thread T0
    #0 0x5624235f0ccb in copy(void*, void*)
/home/martin/code/llvm/build/densemap.cpp:45
    #1 0x5624235f0ccb in main /home/martin/code/llvm/build/densemap.cpp:59
    #2 0x7f33b744bb96 in __libc_start_main
(/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x5624235f1089 in _start (/home/martin/code/llvm/build/densemap+0x4089)

0x6190000000f8 is located 120 bytes inside of 1024-byte region
[0x619000000080,0x619000000480)
freed by thread T0 here:
    #0 0x7f33b78fc2d0 in operator delete(void*)
(/usr/lib/x86_64-linux-gnu/libasan.so.4+0xe12d0)
    #1 0x5624235f069f in llvm::DenseMap<void*, void*,
llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*>
>::grow(unsigned int) ../include/llvm/ADT/DenseMap.h:812
    #2 0x5624235f069f in llvm::DenseMapBase<llvm::DenseMap<void*, void*,
llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*> >, void*,
void*, llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*>
>::grow(unsigned int) ../include/llvm/ADT/DenseMap.h:533
    #3 0x5624235f069f in llvm::detail::DenseMapPair<void*, void*>*
llvm::DenseMapBase<llvm::DenseMap<void*, void*, llvm::DenseMapInfo<void*>,
llvm::detail::DenseMapPair<void*, void*> >, void*, void*,
llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*>
>::InsertIntoBucketImpl<void*>(void* const&, void* const&,
llvm::detail::DenseMapPair<void*, void*>*) ../include/llvm/ADT/DenseMap.h:577
    #4 0x5624235f069f in llvm::detail::DenseMapPair<void*, void*>*
llvm::DenseMapBase<llvm::DenseMap<void*, void*, llvm::DenseMapInfo<void*>,
llvm::detail::DenseMapPair<void*, void*> >, void*, void*,
llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*>
>::InsertIntoBucket<void* const&>(llvm::detail::DenseMapPair<void*, void*>*,
void* const&) ../include/llvm/ADT/DenseMap.h:543
    #5 0x5624235f069f in llvm::DenseMapBase<llvm::DenseMap<void*, void*,
llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*> >, void*,
void*, llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*>
>::FindAndConstruct(void* const&) ../include/llvm/ADT/DenseMap.h:322
    #6 0x5624235f069f in llvm::DenseMapBase<llvm::DenseMap<void*, void*,
llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*> >, void*,
void*, llvm::DenseMapInfo<void*>, llvm::detail::DenseMapPair<void*, void*>
>::operator[](void* const&) ../include/llvm/ADT/DenseMap.h:326
    #7 0x5624235f069f in copy(void*, void*)
/home/martin/code/llvm/build/densemap.cpp:45
    #8 0x5624235f069f in main /home/martin/code/llvm/build/densemap.cpp:59

The testcase also can be tweaked (by changing ValueType to LargeValue instead
of void*) to trigger the same issue when built with Clang as well, and can be
tweaked to test two different workarounds for the issue, one that helps for
Clang and one that helps for both.

A fix proposal has been submitted at https://reviews.llvm.org/D62624.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190529/fed168f4/attachment.html>