circt icon indicating copy to clipboard operation
circt copied to clipboard

Published 20 hours ago • verified publisher icon llvm

Dedup iterator invalidation bug

Open dtzSiFive opened this issue 3 years ago • 2 comments
trafficstars

Summary

Dedup pass appears to still have a safety issue re:early-inc/post-order iterators over a mutated instance graph.

Ran into this using a recent (post-1.4.0) firtool, reported by ASAN.

Details

ASAN report 
=================================================================
==830554==ERROR: AddressSanitizer: heap-use-after-free on address 0x61600014c2a0 at pc 0x000001255169 bp 0x7ffd1e196e90 sp 0x7ffd1e196e88
READ of size 8 at 0x61600014c2a0 thread T0
    #0 0x1255168 in (anonymous namespace)::DedupPass::runOnOperation() /home/will/src/sifive/circt/lib/Dialect/FIRRTL/Transforms/Dedup.cpp:1190:21
    #1 0x228db02 in mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:470:11
    #2 0x228f2b3 in mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:534:16
    #3 0x22a22af in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12::operator()(mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo&) const /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:754:36
    #4 0x22924e2 in failableParallelForEach<__gnu_cxx::__normal_iterator<OpPMInfo *, std::vector<OpPMInfo, std::allocator<OpPMInfo> > >, (lambda at /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:744:20) &> /home/will/src/sifive/circt/llvm/mlir/include/mlir/IR/Threading.h:46:18
    #5 0x22924e2 in failableParallelForEach<std::vector<OpPMInfo, std::allocator<OpPMInfo> > &, (lambda at /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:744:20) &> /home/will/src/sifive/circt/llvm/mlir/include/mlir/IR/Threading.h:92:10
    #6 0x22924e2 in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:764:14
    #7 0x228de03 in runOnOperation /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:655:5
    #8 0x228de03 in mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:468:14
    #9 0x228f2b3 in mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:534:16
    #10 0x2295522 in runPasses /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:837:10
    #11 0x2295522 in mlir::PassManager::run(mlir::Operation*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:817:60
    #12 0xdb6bf6 in processBuffer(mlir::MLIRContext&, mlir::TimingScope&, llvm::SourceMgr&, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:624:17
    #13 0xdb3cba in processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer> >, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:714:12
    #14 0xdb388e in processInput(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer> >, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:730:12
    #15 0xdb34f4 in executeFirtool(mlir::MLIRContext&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:811:14
    #16 0xdb2bed in main /home/will/src/sifive/circt/tools/firtool/firtool.cpp:846:17
    #17 0x7f0a01f6b236 in __libc_start_call_main (/nix/store/lyl6nysc3i3aqhj6shizjgj0ibnf1pvg-glibc-2.34-210/lib/libc.so.6+0x29236) (BuildId: c512f38583c48b03cc0011d4583d15cea2e94d03)
    #18 0x7f0a01f6b2f4 in __libc_start_main@GLIBC_2.2.5 (/nix/store/lyl6nysc3i3aqhj6shizjgj0ibnf1pvg-glibc-2.34-210/lib/libc.so.6+0x292f4) (BuildId: c512f38583c48b03cc0011d4583d15cea2e94d03)
    #19 0xcbbf70 in _start /build/glibc-2.34/csu/../sysdeps/x86_64/start.S:116

0x61600014c2a0 is located 288 bytes inside of 544-byte region [0x61600014c180,0x61600014c3a0)
freed by thread T0 here:
LLVMSymbolizer: error reading file: No such file or directory
    #0 0xd6b597 in __interceptor_free.part.0 static-reloc.c
    #1 0x125ac5a in llvm::po_iterator<circt::firrtl::InstanceGraph*, llvm::SmallPtrSet<circt::hw::InstanceGraphNode*, 8u>, false, llvm::GraphTraits<circt::firrtl::InstanceGraph*> >::~po_iterator() /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/PostOrderIterator.h:96:7
    #2 0x125ac5a in llvm::early_inc_iterator_impl<llvm::po_iterator<circt::firrtl::InstanceGraph*, llvm::SmallPtrSet<circt::hw::InstanceGraphNode*, 8u>, false, llvm::GraphTraits<circt::firrtl::InstanceGraph*> > >::operator*() /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/STLExtras.h:573:5
    #3 0x125490e in (anonymous namespace)::DedupPass::runOnOperation() /home/will/src/sifive/circt/lib/Dialect/FIRRTL/Transforms/Dedup.cpp:1190:21
    #4 0x228db02 in mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:470:11
    #5 0x228f2b3 in mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:534:16
    #6 0x22a22af in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12::operator()(mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo&) const /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:754:36
    #7 0x22924e2 in failableParallelForEach<__gnu_cxx::__normal_iterator<OpPMInfo *, std::vector<OpPMInfo, std::allocator<OpPMInfo> > >, (lambda at /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:744:20) &> /home/will/src/sifive/circt/llvm/mlir/include/mlir/IR/Threading.h:46:18
    #8 0x22924e2 in failableParallelForEach<std::vector<OpPMInfo, std::allocator<OpPMInfo> > &, (lambda at /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:744:20) &> /home/will/src/sifive/circt/llvm/mlir/include/mlir/IR/Threading.h:92:10
    #9 0x22924e2 in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:764:14
    #10 0x228de03 in runOnOperation /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:655:5
    #11 0x228de03 in mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:468:14
    #12 0x228f2b3 in mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:534:16
    #13 0x2295522 in runPasses /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:837:10
    #14 0x2295522 in mlir::PassManager::run(mlir::Operation*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:817:60
    #15 0xdb6bf6 in processBuffer(mlir::MLIRContext&, mlir::TimingScope&, llvm::SourceMgr&, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:624:17
    #16 0xdb3cba in processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer> >, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:714:12
    #17 0xdb388e in processInput(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer> >, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:730:12
    #18 0xdb34f4 in executeFirtool(mlir::MLIRContext&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:811:14
    #19 0xdb2bed in main /home/will/src/sifive/circt/tools/firtool/firtool.cpp:846:17
    #20 0x7f0a01f6b236 in __libc_start_call_main (/nix/store/lyl6nysc3i3aqhj6shizjgj0ibnf1pvg-glibc-2.34-210/lib/libc.so.6+0x29236) (BuildId: c512f38583c48b03cc0011d4583d15cea2e94d03)
    #21 0x7ffd1e19b8e5  ([stack]+0x428e5)

previously allocated by thread T0 here:
    #0 0xd6c49f in malloc (/home/will/src/sifive/circt/build-asan/bin/firtool+0xd6c49f)
    #1 0xe3a545 in safe_malloc /home/will/src/sifive/circt/llvm/llvm/include/llvm/Support/MemAlloc.h:26:18
    #2 0xe3a545 in llvm::SmallVectorBase<unsigned int>::grow_pod(void*, unsigned long, unsigned long) /home/will/src/sifive/circt/llvm/llvm/lib/Support/SmallVector.cpp:126:15
    #3 0x1209a03 in llvm::SmallVectorTemplateCommon<std::pair<circt::hw::InstanceGraphNode*, llvm::mapped_iterator<circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false> >, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*> >, void>::grow_pod(unsigned long, unsigned long) /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/SmallVector.h:120:11
    #4 0x1209a03 in llvm::SmallVectorTemplateBase<std::pair<circt::hw::InstanceGraphNode*, llvm::mapped_iterator<circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false> >, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*> >, true>::grow(unsigned long) /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/SmallVector.h:506:41
    #5 0x1209a03 in llvm::SmallVectorImpl<std::pair<circt::hw::InstanceGraphNode*, llvm::mapped_iterator<circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false> >, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*> > >::operator=(llvm::SmallVectorImpl<std::pair<circt::hw::InstanceGraphNode*, llvm::mapped_iterator<circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false> >, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*> > > const&) /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/SmallVector.h:1026:11
    #6 0x125ac3e in llvm::po_iterator<circt::firrtl::InstanceGraph*, llvm::SmallPtrSet<circt::hw::InstanceGraphNode*, 8u>, false, llvm::GraphTraits<circt::firrtl::InstanceGraph*> >::operator++(int) /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/PostOrderIterator.h:176:23
    #7 0x125ac3e in llvm::early_inc_iterator_impl<llvm::po_iterator<circt::firrtl::InstanceGraph*, llvm::SmallPtrSet<circt::hw::InstanceGraphNode*, 8u>, false, llvm::GraphTraits<circt::firrtl::InstanceGraph*> > >::operator*() /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/STLExtras.h:573:13
    #8 0x125490e in (anonymous namespace)::DedupPass::runOnOperation() /home/will/src/sifive/circt/lib/Dialect/FIRRTL/Transforms/Dedup.cpp:1190:21
    #9 0x228db02 in mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:470:11
    #10 0x228f2b3 in mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:534:16
    #11 0x22a22af in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12::operator()(mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo&) const /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:754:36
    #12 0x22924e2 in failableParallelForEach<__gnu_cxx::__normal_iterator<OpPMInfo *, std::vector<OpPMInfo, std::allocator<OpPMInfo> > >, (lambda at /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:744:20) &> /home/will/src/sifive/circt/llvm/mlir/include/mlir/IR/Threading.h:46:18
    #13 0x22924e2 in failableParallelForEach<std::vector<OpPMInfo, std::allocator<OpPMInfo> > &, (lambda at /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:744:20) &> /home/will/src/sifive/circt/llvm/mlir/include/mlir/IR/Threading.h:92:10
    #14 0x22924e2 in mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:764:14
    #15 0x228de03 in runOnOperation /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:655:5
    #16 0x228de03 in mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:468:14
    #17 0x228f2b3 in mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:534:16
    #18 0x2295522 in runPasses /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:837:10
    #19 0x2295522 in mlir::PassManager::run(mlir::Operation*) /home/will/src/sifive/circt/llvm/mlir/lib/Pass/Pass.cpp:817:60
    #20 0xdb6bf6 in processBuffer(mlir::MLIRContext&, mlir::TimingScope&, llvm::SourceMgr&, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:624:17
    #21 0xdb3cba in processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer> >, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:714:12
    #22 0xdb388e in processInput(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer> >, llvm::Optional<std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile> > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:730:12
    #23 0xdb34f4 in executeFirtool(mlir::MLIRContext&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:811:14
    #24 0xdb2bed in main /home/will/src/sifive/circt/tools/firtool/firtool.cpp:846:17
    #25 0x7f0a01f6b236 in __libc_start_call_main (/nix/store/lyl6nysc3i3aqhj6shizjgj0ibnf1pvg-glibc-2.34-210/lib/libc.so.6+0x29236) (BuildId: c512f38583c48b03cc0011d4583d15cea2e94d03)
    #26 0x7ffd1e19b8e5  ([stack]+0x428e5)

The SmallVector of pairs looks to be the visit stack stored in post-order iterators.

So it looks like the post-order iterator's state -- despite (because of?) make_early_inc_range wrapping it-- does not work well when mutating the underlying graph. (Would external storage would help?)

dtzSiFive avatar Jun 21 '22 03:06 dtzSiFive

Observations

Debugged this a little, and tried a few alternate approaches just to see what's going on. I need to step away from this for now, but in case it's useful/interesting:

One simple answer is stashing the post-order list of modules into a vector and iterating on that, no make_early_inc_range needed. This appears to work re:valgrind/ASAN at least on the triggering input design. Good, that makes sense. here.

What was a bit more surprising is when I dropped make_early_inc_range and manually did the same ((for auto I = po_begin(G), E= po_end(G); I != E;) { auto *X = *I++; /* .. */ } pattern) the errors went away too...? So maybe po_iterator doesn't work well with make_early_inc_range? I'm not sure! More investigation/testing needed. here.

I may be missing something re:the above, please let me know :wink:, but anyway this would be good to fix! Have not observed a crash in practice from this, FWIW.

dtzSiFive avatar Jun 21 '22 03:06 dtzSiFive

I copied the std::vector solution in https://github.com/llvm/circt/pull/3390, but I think we should leave this issue open to track down what is actually going on and see if we can find a better solution.

youngar avatar Jun 21 '22 17:06 youngar

In this post[0] (can't wait, love the pipe syntax and views re:c++20/rangev3) it mentions a known problem with some LLVM bits, particularly mapped_iterator.

This is explained by a linked post[1] which describes a problem combining iterator with logic in operator++ with one with logic in operator*, which sure sounds like mapped_iterator and early_inc.

I think this means it'll be fixed soon-ish, perhaps with the copy-assignable PR[2] or otherwise, and if nothing else explains what we were seeing!

[0] https://discourse.llvm.org/t/rfc-extend-ranges-infrastructure-to-better-match-c-20/65377 [1] https://www.fluentcpp.com/2019/04/16/an-alternative-design-to-iterators-and-ranges-using-stdoptional/ [2] https://reviews.llvm.org/D134675

dtzSiFive avatar Sep 27 '22 13:09 dtzSiFive