Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

testSubgraphPreconditioner bad_alloc exception under i386 #182

Closed
jlblancoc opened this issue Dec 7, 2019 · 7 comments · Fixed by #183
Closed

testSubgraphPreconditioner bad_alloc exception under i386 #182

jlblancoc opened this issue Dec 7, 2019 · 7 comments · Fixed by #183
Labels
bug Bug report

Comments

@jlblancoc
Copy link
Member

Another spin off of #168 .

Building for i386, the unit test testSubgraphPreconditioner fails.
Here's a gdb stack trace:

Thread 1 "testSubgraphPre" hit Catchpoint 1 (exception thrown), 0xb7a0d426 in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
(gdb) bt
#0  0xb7a0d426 in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#1  0x0044eaf6 in Eigen::internal::throw_std_bad_alloc() ()
#2  0xb7e56d70 in gtsam::getSubvector(Eigen::Matrix<double, -1, 1, 0, -1, 1> const&, gtsam::KeyInfo const&, std::vector<unsigned long long, tbb::tbb_allocator<unsigned long long> > const&) ()
   from /home/jlblanco/code/gtsam/build/gtsam/libgtsam.so.4
#3  0xb7e59c22 in gtsam::SubgraphPreconditioner::solve(Eigen::Matrix<double, -1, 1, 0, -1, 1> const&, Eigen::Matrix<double, -1, 1, 0, -1, 1>&) const ()
   from /home/jlblanco/code/gtsam/build/gtsam/libgtsam.so.4
#4  0x004432f8 in SubgraphSolverSolvesTest::run(TestResult&) ()
#5  0x0046ee4c in TestRegistry::run(TestResult&) ()
#6  0x0046f45d in TestRegistry::runAllTests(TestResult&) ()
#7  0x004398da in main ()

Will have to re-run with debug info to investigate what's wrong...

@ProfFan
Copy link
Collaborator

ProfFan commented Dec 22, 2019

I tested on a i386 box with gcc 5.4.0 on DigitalOcean:

 33/240 Test  #33: testPose2 ..............................***Exception: SegFault  0.12 sec

 41/240 Test  #41: testPose3 ..............................***Failed    0.01 sec
not equal:
expected = [
 	       1        0        0        0 0.160001 0.119999;
    	       0     -0.8     -0.6      0.2        0        0
  ]
actual = [
 	   1    0    0   -0 0.16 0.12;
    	  -0 -0.8 -0.6  0.2    0    0
  ]
actual - expected = [
 	-7.77686e-08            0            0           -0 -1.17911e-06  7.38653e-07;
    	          -0  1.66678e-07  3.70296e-08  4.44531e-07            0            0
  ]
/root/gtsam/gtsam/geometry/tests/testPose3.cpp:663: Failure: "assert_equal(expectedH1, actualH1)"
not equal:
expected = [
 	        0 -0.160001 -0.119999;
    	     -0.2         0         0
  ]
actual = [
 	    0 -0.16 -0.12;
    	 -0.2     0     0
  ]
actual - expected = [
 	           0  1.17898e-06 -7.38653e-07;
    	-4.44531e-07            0            0
  ]
/root/gtsam/gtsam/geometry/tests/testPose3.cpp:664: Failure: "assert_equal(expectedH2, actualH2)"
There were 2 failures

        Start  42: testOrientedPlane3
 42/240 Test  #42: testOrientedPlane3 .....................***Failed    0.02 sec
not equal:
expected = [
 	   0.993351 -0.00355884           0;
    	-0.00309235    0.998336           0;
    	          0           0           1
  ]
actual = [
 	   0.993351 -0.00355884           0;
    	-0.00309235    0.998337           0;
    	          0           0           1
  ]
actual - expected = [
 	-3.34242e-07 -1.00049e-09            0;
    	 1.04166e-09  2.80199e-07            0;
    	           0            0 -6.55098e-12
  ]
/root/gtsam/gtsam/geometry/tests/testOrientedPlane3.cpp:174: Failure: "assert_equal(H_expected_numerical, H_actual, 1e-9)"
not equal:
expected = [
 	           1  1.63311e-12            0;
    	-4.51534e-13            1            0;
    	           0            0            1
  ]
actual = [
 	          1 4.92223e-18           0;
    	2.42935e-19           1           0;
    	          0           0           1
  ]
actual - expected = [
 	-2.25501e-07 -1.63311e-12            0;
    	 4.51535e-13 -1.98395e-07            0;
    	           0            0  3.78578e-11
  ]
/root/gtsam/gtsam/geometry/tests/testOrientedPlane3.cpp:180: Failure: "assert_equal(H_expected_numerical, H_actual, 1e-9)"
There were 2 failures

 48/240 Test  #48: testUnit3 ..............................***Exception: SegFault  0.13 sec
not equal:
expected = [
 	  0.998321  -0.013266;
    	0.00666626   0.993267
  ]
actual = [
 	  0.998321  -0.013266;
    	0.00666625   0.993267
  ]
actual - expected = [
 	-4.84334e-07  2.26646e-09;
    	-3.23402e-09 -1.69693e-07
  ]
/root/gtsam/gtsam/geometry/tests/testUnit3.cpp:384: Failure: "assert_equal(H_expected_numerical, H, 1e-9)"
not equal:
expected = [
 	-1.53954e-12     0.222374      0.14825;
    	   -0.257541   -0.0396212    0.0594323
  ]
actual = [
 	-6.77626e-18     0.222375      0.14825;
    	   -0.257539   -0.0396214    0.0594322
  ]
actual - expected = [
 	 1.53953e-12  1.15186e-06 -2.69315e-07;
    	 1.23771e-06 -2.05232e-07 -1.07966e-07
  ]

54/240 Test  #54: testPoint2 .............................***Exception: SegFault  0.12 sec

95/240 Test  #95: testRegularHessianFactor ...............***Exception: SegFault  0.13 sec

        Start 131: testGeneralSFMFactor_Cal3Bundler
131/240 Test #131: testGeneralSFMFactor_Cal3Bundler .......***Exception: SegFault  0.13 sec

        Start 132: testRotateFactor
132/240 Test #132: testRotateFactor .......................   Passed    0.01 sec
        Start 133: testSlamExpressions
133/240 Test #133: testSlamExpressions ....................   Passed    0.01 sec
        Start 134: testGeneralSFMFactor
134/240 Test #134: testGeneralSFMFactor ...................***Exception: SegFault  0.13 sec
149/240 Test #149: testGraph ..............................***Exception: SegFault  0.11 sec

159/240 Test #159: testPCGSolver ..........................***Failed    5.61 sec
/root/gtsam/tests/testPCGSolver.cpp:129: Failure: "Exception: Requested variable 'x1' is not in this VectorValues."
/root/gtsam/tests/testPCGSolver.cpp:150: Failure: "Exception: std::bad_array_new_length"
/root/gtsam/tests/testPCGSolver.cpp:171: Failure: "Exception: Requested variable 'x1' is not in this VectorValues."
There were 3 failures
162/240 Test #162: testSubgraphPreconditioner .............***Exception: SegFault  0.12 sec

185/240 Test #185: testSimPolygon2D .......................***Exception: SegFault  0.13 sec

202/240 Test #202: testIMUSystem ..........................***Exception: SegFault  0.13 sec

218/239 Test #218: testTSAMFactors ........................***Exception: SegFault  0.12 sec
        Start 219: testSmartRangeFactor
219/239 Test #219: testSmartRangeFactor ...................***Exception: SegFault  0.13 sec

The following tests FAILED:
	 33 - testPose2 (SEGFAULT)
	 41 - testPose3 (Failed)
	 42 - testOrientedPlane3 (Failed)
	 48 - testUnit3 (SEGFAULT)
	 54 - testPoint2 (SEGFAULT)
	 95 - testRegularHessianFactor (SEGFAULT)
	131 - testGeneralSFMFactor_Cal3Bundler (SEGFAULT)
	134 - testGeneralSFMFactor (SEGFAULT)
	149 - testGraph (SEGFAULT)
	159 - testPCGSolver (Failed)
	162 - testSubgraphPreconditioner (SEGFAULT)
	185 - testSimPolygon2D (SEGFAULT)
	202 - testIMUSystem (SEGFAULT)
	218 - testTSAMFactors (SEGFAULT)
	219 - testSmartRangeFactor (SEGFAULT)

One test hangs: testConcurrentIncrementalSmootherDL.

@ProfFan

This comment has been minimized.

@ProfFan

This comment has been minimized.

@ProfFan
Copy link
Collaborator

ProfFan commented Dec 23, 2019

Now everything points to

==9749==ERROR: AddressSanitizer: stack-buffer-overflow on address 0xbfe157cc at pc 0xb658912a bp 0xbfe15788 sp 0xbfe15780
READ of size 4 at 0xbfe157cc thread T0
    #0 0xb6589129 in gtsam::KeyInfo::initialize(gtsam::GaussianFactorGraph const&) /root/gtsam/gtsam/linear/IterativeSolver.cpp:121:30
    #1 0xb65894dc in gtsam::KeyInfo::KeyInfo(gtsam::GaussianFactorGraph const&) /root/gtsam/gtsam/linear/IterativeSolver.cpp:108:3
    #2 0x823b6c4 in SubgraphSolverSolvesTest::run(TestResult&) /root/gtsam/tests/testSubgraphPreconditioner.cpp:228:13
    #3 0x83c5a4c in TestRegistry::run(TestResult&) /root/gtsam/CppUnitLite/TestRegistry.cpp:62:15
    #4 0x83c558f in TestRegistry::runAllTests(TestResult&) /root/gtsam/CppUnitLite/TestRegistry.cpp:29:22
    #5 0x824047c in main /root/gtsam/tests/testSubgraphPreconditioner.cpp:314:10
    #6 0xb44fd636 in __libc_start_main /build/glibc-GoSbp4/glibc-2.23/csu/../csu/libc-start.c:291
    #7 0x8180c44 in _start (/root/gtsam_build/tests/testSubgraphPreconditioner+0x8180c44)

Address 0xbfe157cc is located in stack of thread T0 at offset 44 in frame
    #0 0xb6588bff in gtsam::KeyInfo::initialize(gtsam::GaussianFactorGraph const&) /root/gtsam/gtsam/linear/IterativeSolver.cpp:112

  This frame has 7 object(s):
    [16, 40) 'colspec' (line 113) <== Memory access at offset 44 overflows this variable
    [80, 84) 'key' (line 118)
    [96, 100) 'item' (line 119)
    [112, 120) 'ref.tmp' (line 119)
    [144, 148) 'ref.tmp5' (line 120)
    [160, 172) 'ref.tmp13' (line 122)
    [192, 200) 'tmp' (line 122)
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)
SUMMARY: AddressSanitizer: stack-buffer-overflow /root/gtsam/gtsam/linear/IterativeSolver.cpp:121:30 in gtsam::KeyInfo::initialize(gtsam::GaussianFactorGraph const&)
Shadow bytes around the buggy address:
  0x37fc2aa0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x37fc2ab0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x37fc2ac0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x37fc2ad0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x37fc2ae0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x37fc2af0: 00 00 00 00 f1 f1 00 00 00[f2]f2 f2 f2 f2 04 f2
  0x37fc2b00: 04 f2 f8 f2 f2 f2 f8 f2 f8 f8 f2 f2 f8 f3 f3 f3
  0x37fc2b10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x37fc2b20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x37fc2b30: 00 00 00 00 00 00 00 00 00 00 00 00 f1 f1 00 00
  0x37fc2b40: 00 00 00 00 00 00 00 00 00 00 00 00 f2 f2 f2 f2
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==9749==ABORTING

@ProfFan
Copy link
Collaborator

ProfFan commented Dec 23, 2019

(cont.d) whose reason is that const map<Key, size_t> colspec = fg.getKeyDimMap(); does not have the key.

This maps to that fg.getKeyDimMap() is misbehaving.

SIZE: 9
[8646911284551353321, 1001, 2], [8646911284551353322, 1002, 2], [8646911284551353323, 1003, 2], [8646911284551354321, 2001, 2], [8646911284551354322, 2002, 2], [8646911284551354323, 2003, 2], [8646911284551355321, 3001, 2], [8646911284551355322, 3002, 2], [8646911284551355323, 3003, 2],
KEY:1001
1

Note that 8646911284551353321 is 0x78*2^{63-8}+1001, and (size_t) k is indeed 1001.

@jlblancoc @dellaert
In short, the issue is with the wrong assumption that size_t is the same type with Key (uint_64 always).

void KeyInfo::initialize(const GaussianFactorGraph &fg) {
  const map<Key, size_t> colspec = fg.getKeyDimMap();
  const size_t n = ordering_.size();
  size_t start = 0;
  cout << "SIZE: " << colspec.size() << endl;
  for (const auto &[k, v] : colspec)
    cout << "[" << k << ", " << (size_t)k << ", " << v << "], ";
  cout << endl;
  for (size_t i = 0; i < n; ++i) {
    const size_t key = ordering_[i];
    cout << "KEY:" << key << endl;
    auto item = colspec.find(key);
    cout << (item == colspec.end()) << endl;
    const size_t dim = item->second;
    this->emplace(key, KeyInfoEntry(i, dim, start));
    start += dim;
  }
  numCols_ = start;
}

@dellaert
Copy link
Member

dellaert commented Dec 23, 2019 via email

@jlblancoc
Copy link
Member Author

Great debugging! 👍

I think the line to blame is 118 in IterativeSolver.cpp

    const size_t key = ordering_[i];

Will open a PR for you to test, @ProfFan .

dellaert added a commit that referenced this issue Dec 23, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Bug report
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants