search

llvm / circt

Circuit IR Compilers and Tools
https://circt.org
Other
1.69k stars 302 forks source link

Dedup iterator invalidation bug #3387

Open dtzSiFive opened 2 years ago

dtzSiFive commented 2 years ago

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 > >, (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 > &, (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 > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:624:17 #13 0xdb3cba in processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr >, llvm::Optional > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:714:12 #14 0xdb388e in processInput(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr >, llvm::Optional > >&) /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, false, llvm::GraphTraits >::~po_iterator() /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/PostOrderIterator.h:96:7 #2 0x125ac5a in llvm::early_inc_iterator_impl, false, llvm::GraphTraits > >::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 > >, (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 > &, (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 > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:624:17 #16 0xdb3cba in processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr >, llvm::Optional > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:714:12 #17 0xdb388e in processInput(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr >, llvm::Optional > >&) /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::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, 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, 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, false, false> >, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*> > >::operator=(llvm::SmallVectorImpl, 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, false, llvm::GraphTraits >::operator++(int) /home/will/src/sifive/circt/llvm/llvm/include/llvm/ADT/PostOrderIterator.h:176:23 #7 0x125ac3e in llvm::early_inc_iterator_impl, false, llvm::GraphTraits > >::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 > >, (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 > &, (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 > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:624:17 #21 0xdb3cba in processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr >, llvm::Optional > >&) /home/will/src/sifive/circt/tools/firtool/firtool.cpp:714:12 #22 0xdb388e in processInput(mlir::MLIRContext&, mlir::TimingScope&, std::unique_ptr >, llvm::Optional > >&) /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 commented 2 years ago

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.

youngar commented 2 years ago

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.

dtzSiFive commented 2 years ago

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