[mlpack-svn] [MLPACK] #368: invalid memory access during XTreeSplit

[MLPACK Trac]

#368: invalid memory access during XTreeSplit
---------------------+------------------------------------------------------
 Reporter:  rcurtin  |        Owner:                       
     Type:  defect   |       Status:  new                  
 Priority:  minor    |    Milestone:  mlpack 1.1.0         
Component:  mlpack   |     Keywords:  x tree, rectangletree
 Blocking:           |   Blocked By:                       
---------------------+------------------------------------------------------
 There are some invalid memory accesses with the XTreeSplit code that can
 cause all manner of bad things: the program may crash, it may luckily
 complete with error (I guess this thing isn't bad), or the tree may enter
 a very weird state that allows infinite loops.  I believe this is due to
 improper use of std::vector for the children.  In r17184, I've worked one
 of these issues out, but valgrind suggests that there are more:

 {{{
 :[ ~/work/fastlab/mlpack/trunk/build ]: 24
 :[ ryan @ trevelyan ]: $ valgrind bin/mlpack_test -t
 RectangleTreeTest/XTreeTraverserTest
 ==2717== Memcheck, a memory error detector
 ==2717== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
 ==2717== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
 ==2717== Command: bin/mlpack_test -t RectangleTreeTest/XTreeTraverserTest
 ==2717==
 Running 1 test case...
 ==2717== Invalid write of size 8
 ==2717==    at 0xB53AC1:
 mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double>
 >::SplitNonLeafNode(mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >*, std::vector<bool, std::allocator<bool> >&)
 (x_tree_split_impl.hpp:683)
 ==2717==    by 0xB4FB91:
 mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double>
 >::SplitNonLeafNode(mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >*, std::vector<bool, std::allocator<bool> >&)
 (x_tree_split_impl.hpp:270)
 ==2717==    by 0xB4F6A4:
 mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double>
 >::SplitLeafNode(mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >*, std::vector<bool, std::allocator<bool> >&)
 (x_tree_split_impl.hpp:233)
 ==2717==    by 0xB3F405:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::SplitNode(std::vector<bool, std::allocator<bool> >&)
 (rectangle_tree_impl.hpp:557)
 ==2717==    by 0xB40587:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::InsertPoint(unsigned long, std::vector<bool,
 std::allocator<bool> >&) (rectangle_tree_impl.hpp:236)
 ==2717==    by 0xB40667:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::InsertPoint(unsigned long, std::vector<bool,
 std::allocator<bool> >&) (rectangle_tree_impl.hpp:244)
 ==2717==    by 0xB4D9A5:
 mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double>
 >::SplitLeafNode(mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >*, std::vector<bool, std::allocator<bool> >&)
 (x_tree_split_impl.hpp:74)
 ==2717==    by 0xB3F405:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::SplitNode(std::vector<bool, std::allocator<bool> >&)
 (rectangle_tree_impl.hpp:557)
 ==2717==    by 0xB40587:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::InsertPoint(unsigned long, std::vector<bool,
 std::allocator<bool> >&) (rectangle_tree_impl.hpp:236)
 ==2717==    by 0xB37204:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::InsertPoint(unsigned long)
 (rectangle_tree_impl.hpp:211)
 ==2717==    by 0xB2F21A:
 mlpack::tree::RectangleTree<mlpack::tree::XTreeSplit<mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >, mlpack::tree::RStarTreeDescentHeuristic,
 mlpack::neighbor::NeighborSearchStat<mlpack::neighbor::NearestNeighborSort>,
 arma::Mat<double> >::RectangleTree(arma::Mat<double>&, unsigned long,
 unsigned long, unsigned long, unsigned long, unsigned long)
 (rectangle_tree_impl.hpp:53)
 ==2717==    by 0xB212E7:
 RectangleTreeTest::XTreeTraverserTest::test_method()
 (rectangle_tree_test.cpp:648)
 ==2717==  Address 0x30 is not stack'd, malloc'd or (recently) free'd
 ==2717==
 ==2717== Warning: client switching stacks?  SP change: 0x92aaac8 -->
 0xffefff550
 ==2717==          to suppress, use: --max-stackframe=68548905608 or
 greater
 unknown location(0): fatal error in "XTreeTraverserTest": memory access
 violation at address: 0x00000030: no mapping at fault address

 *** 1 failure detected in test suite "MLPACKTest"
 ==2717==
 ==2717== HEAP SUMMARY:
 ==2717==     in use at exit: 8,218,276 bytes in 81 blocks
 ==2717==   total heap usage: 6,650 allocs, 6,569 frees, 8,625,601 bytes
 allocated
 ==2717==
 ==2717== LEAK SUMMARY:
 ==2717==    definitely lost: 712 bytes in 6 blocks
 ==2717==    indirectly lost: 0 bytes in 0 blocks
 ==2717==      possibly lost: 64,000 bytes in 1 blocks
 ==2717==    still reachable: 8,153,564 bytes in 74 blocks
 ==2717==         suppressed: 0 bytes in 0 blocks
 ==2717== Rerun with --leak-check=full to see details of leaked memory
 ==2717==
 ==2717== For counts of detected and suppressed errors, rerun with: -v
 ==2717== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)
 Profiling timer expired
 }}}

 There are probably more errors to be addressed once that one is fixed.

-- 
Ticket URL: <http://trac.research.cc.gatech.edu/fastlab/ticket/368>
MLPACK <www.fast-lab.org>
MLPACK is an intuitive, fast, and scalable C++ machine learning library developed at Georgia Tech.