search

scipopt / papilo

Parallel Presolve for Integer and Linear Optimization
GNU Lesser General Public License v3.0
64 stars 17 forks source link

Potential segfault from out-of-bounds access #47

Closed jamesjer closed 7 months ago

jamesjer commented 7 months ago

I am seeing segfaults while running the papilo 2.2.0 testsuite on some architectures. The segfault is repeatable on s390x. Valgrind shows an out-of-bounds array access on all architectures, although it doesn't necessarily lead to a segfault:

$ valgrind --leak-check=no --enable-debuginfod=yes --read-inline-info=yes --read-var-info=yes --track-origins=yes bin/papilo solve -a r -f /builddir/build/BUILD/papilo-2.2.0/check/instances/MIP/gt2.mps -o 21166 -p /builddir/build/BUILD/papilo-2.2.0/settings/default.set
==145== Memcheck, a memory error detector
==145== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==145== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==145== Command: bin/papilo solve -a r -f /builddir/build/BUILD/papilo-2.2.0/check/instances/MIP/gt2.mps -o 21166 -p /builddir/build/BUILD/papilo-2.2.0/settings/default.set
==145== 

PaPILO version 2.2.0 [mode: optimized][Solvers: SCIP,SoPlex][GitHash: ]
Copyright (C) 2020-2023 Zuse Institute Berlin (ZIB)

External libraries: 
  Boost    1.83.0    (https://www.boost.org/)
  TBB                Thread building block https://github.com/oneapi-src/oneTBB developed by Intel
  GMP      6.3.0     GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  SCIP     9.0.0     Mixed Integer Programming Solver developed at Zuse Institute Berlin (scip.zib.de) [GitHash: NoGitInfo]
  SoPlex   7.0.0     Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: NoGitInfo]

reading took 2.72 seconds
Numerical Statistics:
 Matrix range    [1e+00,3e+03]
 Objective range [1e+03,8e+03]
 Bounds range    [1e+00,2e+01]
 RHS range       [1e+00,6e+03]
 Dynamism Variables: 3e+03
 Dynamism Rows     : 2e+02

starting presolve of problem /builddir/build/BUILD/papilo-2.2.0/check/instances/MIP/gt2.mps:
  rows:     29
  columns:  188
  int. columns:  188
  cont. columns:  0
  nonzeros: 376

round 0   ( Trivial  ):    0 del cols,    1 del rows,    0 chg bounds,    0 chg sides,    0 chg coeffs,    0 tsx applied,    0 tsx conflicts
round 1   (   Fast   ):   15 del cols,    1 del rows,   16 chg bounds,    0 chg sides,   10 chg coeffs,   27 tsx applied,    0 tsx conflicts
round 2   (   Fast   ):   15 del cols,    1 del rows,   26 chg bounds,    1 chg sides,   11 chg coeffs,   48 tsx applied,    0 tsx conflicts
==145== Invalid read of size 8
==145==    at 0x48BAFA6: boost::multiprecision::backends::gmp_rational::gmp_rational(boost::multiprecision::backends::gmp_rational const&) (gmp.hpp:2387)
==145==    by 0x4A071EE: UnknownInlinedFun (number.hpp:54)
==145==    by 0x4A071EE: papilo::ParallelColDetection<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::execute(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::ProblemUpdate<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Num<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Reductions<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, papilo::Timer const&, int&)::{lambda(int, int)#1}::operator()(int, int) const (ParallelColDetection.hpp:595)
==145==    by 0x4A07848: UnknownInlinedFun (pdqsort.h:152)
==145==    by 0x4A07848: UnknownInlinedFun (pdqsort.h:158)
==145==    by 0x4A07848: void pdqsort_detail::pdqsort_loop<int*, papilo::ParallelColDetection<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::execute(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::ProblemUpdate<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Num<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Reductions<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, papilo::Timer const&, int&)::{lambda(int, int)#1}, false>(int*, int*, papilo::ParallelColDetection<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::execute(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::ProblemUpdate<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Num<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Reductions<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, papilo::Timer const&, int&)::{lambda(int, int)#1}, int, bool) (pdqsort.h:420)
==145==    by 0x4A0875A: UnknownInlinedFun (pdqsort.h:502)
==145==    by 0x4A0875A: papilo::ParallelColDetection<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::execute(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::ProblemUpdate<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Num<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, papilo::Reductions<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, papilo::Timer const&, int&) (ParallelColDetection.hpp:575)
==145==    by 0x494EC94: UnknownInlinedFun (PresolveMethod.hpp:167)
==145==    by 0x494EC94: UnknownInlinedFun (Presolve.hpp:1028)
==145==    by 0x494EC94: UnknownInlinedFun (_utils.h:362)
==145==    by 0x494EC94: UnknownInlinedFun (parallel_for.h:117)
==145==    by 0x494EC94: UnknownInlinedFun (partitioner.h:513)
==145==    by 0x494EC94: tbb::detail::d1::start_for<tbb::detail::d1::blocked_range<int>, papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::run_presolvers(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, std::pair<int, int> const&, papilo::ProblemUpdate<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool&, papilo::Timer const&)::{lambda(tbb::detail::d1::blocked_range<int> const&)#1}, tbb::detail::d1::simple_partitioner const>::execute(tbb::detail::d1::execution_data&) (parallel_for.h:170)
==145==    by 0x6374A8A: UnknownInlinedFun (task_dispatcher.h:323)
==145==    by 0x6374A8A: UnknownInlinedFun (task_dispatcher.h:459)
==145==    by 0x6374A8A: tbb::detail::r1::task_dispatcher::execute_and_wait(tbb::detail::d1::task*, tbb::detail::d1::wait_context&, tbb::detail::d1::task_group_context&) (task_dispatcher.cpp:168)
==145==    by 0x49371EA: papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::run_presolvers(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > const&, std::pair<int, int> const&, papilo::ProblemUpdate<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool&, papilo::Timer const&) (_task.h:191)
==145==    by 0x49433FD: papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::apply(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool)::{lambda()#1}::operator()() const (Presolve.hpp:557)
==145==    by 0x494E8D8: tbb::detail::d1::task_arena_function<papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::apply(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool)::{lambda()#1}, papilo::PresolveResult<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > >::operator()() const (task_arena.h:47)
==145==    by 0x636056D: tbb::detail::r1::task_arena_impl::execute(tbb::detail::d1::task_arena_base&, tbb::detail::d1::delegate_base&) (arena.cpp:796)
==145==    by 0x4A780BA: papilo::PresolveResult<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > tbb::detail::d1::task_arena::execute_impl<papilo::PresolveResult<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >, papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::apply(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool)::{lambda()#1}>(papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::apply(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool)::{lambda()#1}&) [clone .constprop.0] (task_arena.h:251)
==145==    by 0x4933DC9: UnknownInlinedFun (task_arena.h:404)
==145==    by 0x4933DC9: papilo::Presolve<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >::apply(papilo::Problem<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> >&, bool) (Presolve.hpp:979)
==145==  Address 0x751f758 is 8 bytes after a block of size 48,128 alloc'd
==145==    at 0x4842F95: operator new(unsigned long) (vg_replace_malloc.c:483)
==145==    by 0x33AEE4: UnknownInlinedFun (new_allocator.h:151)
==145==    by 0x33AEE4: UnknownInlinedFun (alloc_traits.h:475)
==145==    by 0x33AEE4: UnknownInlinedFun (stl_vector.h:377)
==145==    by 0x33AEE4: UnknownInlinedFun (stl_vector.h:1618)
==145==    by 0x33AEE4: std::vector<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > >::operator=(std::vector<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::gmp_rational, (boost::multiprecision::expression_template_option)1> > > const&) [clone .isra.0] (vector.tcc:238)
==145==    by 0x154FCA: UnknownInlinedFun (SparseStorage.hpp:67)
==145==    by 0x154FCA: UnknownInlinedFun (ConstraintMatrix.hpp:139)
==145==    by 0x154FCA: UnknownInlinedFun (Problem.hpp:64)
==145==    by 0x154FCA: UnknownInlinedFun (Wrappers.hpp:84)
==145==    by 0x154FCA: main (papilo.cpp:216)

(followed by a few more with the same stacktraces).

alexhoen commented 7 months ago

Fixed with commit 80a6e00d

Thanks for reporting and the investigation