triangulator memory corruption

[pca006132]

This tracks the bug mentioned in #160

I managed to reproduce this with address sanitizer enabled, giving some useful backtrace:

[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from Boolean
[ RUN      ] Boolean.Close
=================================================================
==14036==ERROR: AddressSanitizer: attempting free on address which was not malloc()-ed: 0x7fff00b0b510 in thread T0
    #0 0x52ae07 in operator delete(void*) (/home/pca006132/code/manifold/build/test/manifold_test+0x52ae07)
    #1 0x5c55bb in __gnu_cxx::new_allocator<std::_List_node<(anonymous namespace)::Monotones::EdgePair> >::deallocate(std::_List_node<(anonymous namespace)::Monotones::EdgePair>*, unsigned long) /nix/store/as1xzrm2921pnxx4jvxj39jn4v88wdy1-gcc-11.3.0/include/c++/11.3.0/ext/new_allocator.h:145:2
    #2 0x5c55bb in std::allocator_traits<std::allocator<std::_List_node<(anonymous namespace)::Monotones::EdgePair> > >::deallocate(std::allocator<std::_List_node<(anonymous namespace)::Monotones::EdgePair> >&, std::_List_node<(anonymous namespace)::Monotones::EdgePair>*, unsigned long) /nix/store/as1xzrm2921pnxx4jvxj39jn4v88wdy1-gcc-11.3.0/include/c++/11.3.0/bits/alloc_traits.h:496:13
    #3 0x5c55bb in std::__cxx11::_List_base<(anonymous namespace)::Monotones::EdgePair, std::allocator<(anonymous namespace)::Monotones::EdgePair> >::_M_put_node(std::_List_node<(anonymous namespace)::Monotones::EdgePair>*) /nix/store/as1xzrm2921pnxx4jvxj39jn4v88wdy1-gcc-11.3.0/include/c++/11.3.0/bits/stl_list.h:446:9
    #4 0x5c55bb in std::__cxx11::_List_base<(anonymous namespace)::Monotones::EdgePair, std::allocator<(anonymous namespace)::Monotones::EdgePair> >::_M_clear() /nix/store/as1xzrm2921pnxx4jvxj39jn4v88wdy1-gcc-11.3.0/include/c++/11.3.0/bits/list.tcc:81:4
    #5 0x5c55bb in std::__cxx11::_List_base<(anonymous namespace)::Monotones::EdgePair, std::allocator<(anonymous namespace)::Monotones::EdgePair> >::~_List_base() /nix/store/as1xzrm2921pnxx4jvxj39jn4v88wdy1-gcc-11.3.0/include/c++/11.3.0/bits/stl_list.h:499:9
    #6 0x5c55bb in (anonymous namespace)::Monotones::~Monotones() /home/pca006132/code/manifold/src/polygon/src/polygon.cpp:65:7
    #7 0x5c55bb in manifold::Triangulate(std::vector<std::vector<manifold::PolyVert, std::allocator<manifold::PolyVert> >, std::allocator<std::vector<manifold::PolyVert, std::allocator<manifold::PolyVert> > > > const&, float) /home/pca006132/code/manifold/src/polygon/src/polygon.cpp:922:3
    #8 0x76ca66 in manifold::Manifold::Impl::Face2Tri(manifold::VecDH<int> const&, manifold::VecDH<manifold::BaryRef> const&, manifold::VecDH<int> const&) /home/pca006132/code/manifold/src/manifold/src/face_op.cpp:152:41
    #9 0x759cdb in manifold::Boolean3::Result(manifold::Manifold::OpType) const /home/pca006132/code/manifold/src/manifold/src/boolean_result.cpp:682:8
    #10 0x6a4fef in manifold::CsgOpNode::ToLeafNode() const /home/pca006132/code/manifold/src/manifold/src/csg_tree.cpp:289:50
    #11 0x6f0a29 in manifold::Manifold::GetCsgLeafNode() const /home/pca006132/code/manifold/src/manifold/src/manifold.cpp:83:22
    #12 0x6f82fb in manifold::Manifold::IsManifold() const /home/pca006132/code/manifold/src/manifold/src/manifold.cpp:333:10
    #13 0x5a6651 in Boolean_Close_Test::TestBody() /home/pca006132/code/manifold/test/mesh_test.cpp:924:5
    #14 0x665a10 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2443:10
    #15 0x665a10 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2479:14
    #16 0x5fdc8f in testing::Test::Run() /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2517:5
    #17 0x6014db in testing::TestInfo::Run() /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2693:11
    #18 0x602c8f in testing::TestCase::Run() /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2811:28
    #19 0x62b268 in testing::internal::UnitTestImpl::RunAllTests() /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:5177:43
    #20 0x667d50 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2443:10
    #21 0x667d50 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:2479:14
    #22 0x62a09a in testing::UnitTest::Run() /home/pca006132/code/manifold/test/third_party/google_test/googletest/src/gtest.cc:4786:10
    #23 0x5be4de in RUN_ALL_TESTS() /home/pca006132/code/manifold/test/third_party/google_test/googletest/include/gtest/gtest.h:2341:46
    #24 0x5be4de in main /home/pca006132/code/manifold/test/test_main.cpp:56:10
    #25 0x7fa9d7b0d236 in __libc_start_call_main (/nix/store/scd5n7xsn0hh0lvhhnycr9gx0h8xfzsl-glibc-2.34-210/lib/libc.so.6+0x29236)
    #26 0x7fa9d7b0d2f4 in __libc_start_main@GLIBC_2.2.5 (/nix/store/scd5n7xsn0hh0lvhhnycr9gx0h8xfzsl-glibc-2.34-210/lib/libc.so.6+0x292f4)
    #27 0x44b8c0 in _start /build/glibc-2.34/csu/../sysdeps/x86_64/start.S:116


Address 0x7ffd43ec2b90 is located in stack of thread T0 at offset 1680 in frame
    #0 0x5be6ff in manifold::Triangulate(std::vector<std::vector<manifold::PolyVert, std::allocator<manifold::PolyVert> >, std::allocator<std::vector<manifold::PolyVert, std::allocator<manifold::PolyVert> > > > const&, float) /home/pca006132/code/manifold/src/polygon/src/polygon.cpp:913

  This frame has 32 object(s):
    [32, 40) '__dnew.i.i249.i'
    [64, 72) '__dnew.i.i234.i'
    [96, 104) '__dnew.i.i202.i'
    [128, 136) '__dnew.i.i.i'
    [160, 264) 'triangulator.i' (line 108)
    [304, 336) 'ref.tmp77.i' (line 130)
    [368, 400) 'ref.tmp81.i' (line 130)
    [432, 464) 'ref.tmp118.i' (line 137)
    [496, 528) 'ref.tmp122.i' (line 137)
    [560, 568) '__dnew.i.i304.i.i'
    [592, 600) '__dnew.i.i272.i.i'
    [624, 656) 'ref.tmp26.i.i' (line 805)
    [688, 720) 'ref.tmp28.i.i' (line 805)
    [752, 784) 'ref.tmp51.i.i' (line 808)
    [816, 848) 'ref.tmp55.i.i' (line 808)
    [880, 888) '__dnew.i.i906.i.i'
    [912, 920) '__dnew.i.i891.i.i'
    [944, 952) '__dnew.i.i850.i.i'
    [976, 984) '__dnew.i.i835.i.i'
    [1008, 1016) '__dnew.i.i636.i.i'
    [1040, 1048) '__dnew.i.i543.i.i'
    [1072, 1080) '__dnew.i.i.i.i'
    [1104, 1136) 'nextAttached.i.i' (line 635)
    [1168, 1200) 'ref.tmp79.i.i' (line 673)
    [1232, 1264) 'ref.tmp83.i.i' (line 673)
    [1296, 1328) 'ref.tmp174.i.i' (line 695)
    [1360, 1392) 'ref.tmp178.i.i' (line 695)
    [1424, 1456) 'ref.tmp236.i.i' (line 702)
    [1488, 1520) 'ref.tmp240.i.i' (line 702)
    [1552, 1584) 'ref.tmp266.i.i' (line 704)
    [1616, 1648) 'ref.tmp270.i.i' (line 704)
    [1680, 1760) 'monotones' (line 917) <== Memory access at offset 1680 is inside this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)

[pca006132]

It seems that inactivePairs_ somehow contains an invalid pointer. Perhaps related to splice iterators: https://stackoverflow.com/questions/143156/splice-on-stdlist-and-iterator-invalidation/143165#143165

Edit: we got a cycle in inactivePairs_.

index d0affe3..c266358 100644
--- a/src/polygon/src/polygon.cpp
+++ b/src/polygon/src/polygon.cpp
@@ -88,10 +88,16 @@ class Monotones {
 
     if (precision_ < 0) precision_ = bound * kTolerance;
 
-    if (SweepForward()) return;
+    if (SweepForward()) {
+      std::cout << "sweepforward return" << std::endl;
+      return;
+    }
     Check();
 
-    if (SweepBack()) return;
+    if (SweepBack()) {
+      std::cout << "sweepback return" << std::endl;
+      return;
+    }
     Check();
   }
 
@@ -141,6 +147,27 @@ class Monotones {
   // A variety of sanity checks on the data structure. Expensive checks are only
   // performed if params.intermediateChecks = true.
   void Check() {
+    std::vector<PairItr> pairs;
+    for (PairItr pair = activePairs_.begin(); pair != activePairs_.end(); pair++) {
+      if (std::find(pairs.begin(), pairs.end(), pair) != pairs.end()) {
+        std::cerr << "cycle" << std::endl;
+        abort();
+      }
+      pairs.push_back(pair);
+    }
+    unsigned int num = pairs.size();
+    for (PairItr pair = inactivePairs_.begin(); pair != inactivePairs_.end(); pair++) {
+      auto iter = std::find(pairs.begin(), pairs.end(), pair);
+      if (iter != pairs.end()) {
+        if (std::distance(pairs.begin(), iter) >= num)
+          std::cerr << "inactivePairs_ cycle" << std::endl;
+        else
+          std::cerr << "duplicate" << std::endl;
+        abort();
+      }
+      pairs.push_back(pair);
+    }
+
     if (!params.intermediateChecks) return;
     std::vector<Halfedge> edges;
     for (VertItr vert = monotones_.begin(); vert != monotones_.end(); vert++) {
@@ -914,7 +941,9 @@ std::vector<glm::ivec3> Triangulate(const Polygons &polys, float precision) {
   std::vector<glm::ivec3> triangles;
   try {
     Monotones monotones(polys, precision);
+    monotones.Check();
     monotones.Triangulate(triangles);
+    monotones.Check();
     if (params.intermediateChecks) {
       CheckTopology(triangles, polys);
       CheckGeometry(triangles, polys, precision);

It seems that the cycle is formed after failed sweep back (return non-zero in sweep back).

[elalish]

Thanks for the analysis! I should be able to use that to spit out a test case polygon. Good sleuthing!

[elalish]

I got address sanitizer working, but your patch isn't printing anything for me. Is there anything else required to repro? Also, if you replace abort() with ALWAYS_ASSERT, then the triangulator will catch the exception and print the problem polygon, which is what we need to make a minimal test case.

[pca006132]

Did you change the max iteration to 10? The current one in master will not trigger the error.

[elalish]

Indeed I did; it fails, but on the munmap_chunk(): invalid pointer or double free or corruption (out) before any of your print statements hit.

[pca006132]

Weird, or maybe the cycle is formed due to memory corruption and compiling this with different options somehow changed the behavior? No idea.

[elalish]

Okay, I managed to dump out the polygon and create a simple repro test.