HiGHS icon indicating copy to clipboard operation
HiGHS copied to clipboard

Published 20 hours ago • verified publisher icon ERGO-Code

TSAN reports Data Race Conditions

Open jacobnzw opened this issue 2 years ago • 5 comments

Hi HiGHS team,

I'm trying to run the following code snippet from the examples/call_highs_from_cpp.cpp in reduced form inside a Catch2 unit test

#include <Catch2/catch.hpp>

#include "highs/Highs.h"

void highs_solve_simple_lp()
{
  // Create and populate a HighsModel instance for the LP
  //
  // Min    f  =  x_0 +  x_1 + 3
  // s.t.                x_1 <= 7
  //        5 <=  x_0 + 2x_1 <= 15
  //        6 <= 3x_0 + 2x_1
  // 0 <= x_0 <= 4; 1 <= x_1
  //
  // Although the first constraint could be expressed as an upper
  // bound on x_1, it serves to illustrate a non-trivial packed
  // column-wise matrix.
  //
  HighsModel model;
  model.lp_.num_col_ = 2;
  model.lp_.num_row_ = 3;
  model.lp_.sense_ = ObjSense::kMinimize;
  model.lp_.offset_ = 3;
  model.lp_.col_cost_ = {1.0, 1.0};
  model.lp_.col_lower_ = {0.0, 1.0};
  model.lp_.col_upper_ = {4.0, 1.0e30};
  model.lp_.row_lower_ = {-1.0e30, 5.0, 6.0};
  model.lp_.row_upper_ = {7.0, 15.0, 1.0e30};
  //
  model.lp_.a_matrix_.format_ = MatrixFormat::kColwise;
  model.lp_.a_matrix_.start_ = {0, 2, 5};
  model.lp_.a_matrix_.index_ = {1, 2, 0, 1, 2};
  model.lp_.a_matrix_.value_ = {1.0, 3.0, 1.0, 2.0, 2.0};

  // Create a Highs instance
  Highs highs;
  CHECK(HighsStatus::kOk == highs.passModel(model));
  CHECK(HighsStatus::kOk == highs.run());
}

TEST_CASE("Solves simple LP problem")
{
  highs_solve_simple_lp();
}

When I use tsan on it and run it under gcc-9, I get the following data races reported. I'm wondering if that's a known issue or perhaps a false positive.

==================
WARNING: ThreadSanitizer: data race (pid=1216756)
  Read of size 8 at 0x7f013c97f0c8 by thread T6:
    #0 HighsSplitDeque::WorkerBunk::waitForNewTask(HighsSplitDeque*) <null> (test_highs+0x8a0138)
    #1 HighsTaskExecutor::run_worker(int) <null> (test_highs+0x89ffb9)
    #2 HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int)::operator()(int) const <null> (test_highs+0x89fee8)
    #3 void std::__invoke_impl<void, HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int), int>(std::__invoke_other, HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int)&&, int&&) <null> (test_highs+0x89fe90)
    #4 std::__invoke_result<HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int), int>::type std::__invoke<HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int), int>(HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int)&&, int&&) <null> (test_highs+0x89fda3)
    #5 void std::thread::_Invoker<std::tuple<HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int), int> >::_M_invoke<0ul, 1ul>(std::_Index_tuple<0ul, 1ul>) <null> (test_highs+0x89fd50)
    #6 std::thread::_Invoker<std::tuple<HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int), int> >::operator()() <null> (test_highs+0x89fce9)
    #7 std::thread::_State_impl<std::thread::_Invoker<std::tuple<HighsTaskExecutor::HighsTaskExecutor(int)::'lambda'(int), int> > >::_M_run() <null> (test_highs+0x89fa9d)
    #8 <null> <null> (libstdc++.so.6+0xd0b0f)

  Previous write of size 8 at 0x7f013c97f0c8 by main thread:
    #0 HighsSplitDeque::injectTaskAndNotify(HighsTask*) <null> (test_highs+0x8a1feb)
    #1 HighsTaskExecutor::shutdown(bool) <null> (test_highs+0x88e329)
    #2 HighsTaskExecutor::ExecutorHandle::~ExecutorHandle() <null> (test_highs+0xadbc4d)
    #3 __call_tls_dtors /build/glibc-e6zv40/glibc-2.23/stdlib/cxa_thread_atexit_impl.c:155 (libc.so.6+0x3a60e)

  Location is heap block of size 524608 at 0x7f013c97f000 allocated by main thread:
    #0 operator new(unsigned long) <null> (test_highs+0x7a4abc)
    #1 highs::cache_aligned::alloc(unsigned long) <null> (test_highs+0x89c2c5)
    #2 std::unique_ptr<HighsSplitDeque, highs::cache_aligned::Deleter<HighsSplitDeque> > highs::cache_aligned::make_unique<HighsSplitDeque, std::shared_ptr<HighsSplitDeque::WorkerBunk>&, std::unique_ptr<HighsSplitDeque, highs::cache_aligned::Deleter<HighsSplitDeque> >*, int&, int&>(std::shared_ptr<HighsSplitDeque::WorkerBunk>&, std::unique_ptr<HighsSplitDeque, highs::cache_aligned::Deleter<HighsSplitDeque> >*&&, int&, int&) <null> (test_highs+0x89c774)
    #3 HighsTaskExecutor::HighsTaskExecutor(int) <null> (test_highs+0x89c403)
    #4 std::shared_ptr<HighsTaskExecutor> highs::cache_aligned::make_shared<HighsTaskExecutor, int&>(int&) <null> (test_highs+0x89c123)
    #5 HighsTaskExecutor::initialize(int) <null> (test_highs+0x89c012)
    #6 highs::parallel::initialize_scheduler(int) <null> (test_highs+0x881f66)
    #7 Highs::run() <null> (test_highs+0x882673)
    #8 highs_solve_simple_lp() <null> (test_highs+0x7a5e2d)
    #9 ____C_A_T_C_H____T_E_S_T____0() <null> (test_highs+0x7a64b3)
    #10 Catch::TestInvokerAsFunction::invoke() const <null> (test_highs+0x7ce45d)
    #11 Catch::TestCase::invoke() const <null> (test_highs+0x7c6b43)
    #12 Catch::RunContext::invokeActiveTestCase() <null> (test_highs+0x7c6a68)
    #13 Catch::RunContext::runCurrentTest(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) <null> (test_highs+0x7c4b4b)
    #14 Catch::RunContext::runTest(Catch::TestCase const&) <null> (test_highs+0x7c4410)
    #15 Catch::(anonymous namespace)::TestGroup::execute() <null> (test_highs+0x7c9b1a)
    #16 Catch::Session::runInternal() <null> (test_highs+0x7c91b3)
    #17 Catch::Session::run() <null> (test_highs+0x7c902c)
    #18 int Catch::Session::run<char>(int, char const* const*) <null> (test_highs+0x7e3a93)
    #19 main <null> (test_highs+0x7e39f8)

  Thread T6 (tid=1216763, running) created by main thread at:
    #0 pthread_create <null> (test_highs+0x760cdd)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xd0da4)
    #2 HighsTaskExecutor::HighsTaskExecutor(int) <null> (test_highs+0x89c4c2)
    #3 std::shared_ptr<HighsTaskExecutor> highs::cache_aligned::make_shared<HighsTaskExecutor, int&>(int&) <null> (test_highs+0x89c123)
    #4 HighsTaskExecutor::initialize(int) <null> (test_highs+0x89c012)
    #5 highs::parallel::initialize_scheduler(int) <null> (test_highs+0x881f66)
    #6 Highs::run() <null> (test_highs+0x882673)
    #7 highs_solve_simple_lp() <null> (test_highs+0x7a5e2d)
    #8 ____C_A_T_C_H____T_E_S_T____0() <null> (test_highs+0x7a64b3)
    #9 Catch::TestInvokerAsFunction::invoke() const <null> (test_highs+0x7ce45d)
    #10 Catch::TestCase::invoke() const <null> (test_highs+0x7c6b43)
    #11 Catch::RunContext::invokeActiveTestCase() <null> (test_highs+0x7c6a68)
    #12 Catch::RunContext::runCurrentTest(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) <null> (test_highs+0x7c4b4b)
    #13 Catch::RunContext::runTest(Catch::TestCase const&) <null> (test_highs+0x7c4410)
    #14 Catch::(anonymous namespace)::TestGroup::execute() <null> (test_highs+0x7c9b1a)
    #15 Catch::Session::runInternal() <null> (test_highs+0x7c91b3)
    #16 Catch::Session::run() <null> (test_highs+0x7c902c)
    #17 int Catch::Session::run<char>(int, char const* const*) <null> (test_highs+0x7e3a93)
    #18 main <null> (test_highs+0x7e39f8)

SUMMARY: ThreadSanitizer: data race in HighsSplitDeque::WorkerBunk::waitForNewTask(HighsSplitDeque*)
==================
==================
WARNING: ThreadSanitizer: data race (pid=1216756)
  Write of size 8 at 0x7f013fa76318 by main thread:
    #0 std::enable_if<__and_<std::__not_<std::__is_tuple_like<HighsTaskExecutor*> >, std::is_move_constructible<HighsTaskExecutor*>, std::is_move_assignable<HighsTaskExecutor*> >::value, void>::type std::swap<HighsTaskExecutor*>(HighsTaskExecutor*&, HighsTaskExecutor*&) <null> (test_highs+0x8a3e92)
    #1 std::__shared_ptr<HighsTaskExecutor, (__gnu_cxx::_Lock_policy)2>::swap(std::__shared_ptr<HighsTaskExecutor, (__gnu_cxx::_Lock_policy)2>&) <null> (test_highs+0x8a3e00)
    #2 std::__shared_ptr<HighsTaskExecutor, (__gnu_cxx::_Lock_policy)2>::reset() <null> (test_highs+0x8a7e3d)
    #3 HighsTaskExecutor::shutdown(bool) <null> (test_highs+0x88e36c)
    #4 HighsTaskExecutor::ExecutorHandle::~ExecutorHandle() <null> (test_highs+0xadbc4d)
    #5 __call_tls_dtors /build/glibc-e6zv40/glibc-2.23/stdlib/cxa_thread_atexit_impl.c:155 (libc.so.6+0x3a60e)

  Previous read of size 8 at 0x7f013fa76318 by thread T2:
    [failed to restore the stack]

  Location is TLS of main thread.

  Thread T2 (tid=1216759, finished) created by main thread at:
    #0 pthread_create <null> (test_highs+0x760cdd)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xd0da4)
    #2 HighsTaskExecutor::HighsTaskExecutor(int) <null> (test_highs+0x89c4c2)
    #3 std::shared_ptr<HighsTaskExecutor> highs::cache_aligned::make_shared<HighsTaskExecutor, int&>(int&) <null> (test_highs+0x89c123)
    #4 HighsTaskExecutor::initialize(int) <null> (test_highs+0x89c012)
    #5 highs::parallel::initialize_scheduler(int) <null> (test_highs+0x881f66)
    #6 Highs::run() <null> (test_highs+0x882673)
    #7 highs_solve_simple_lp() <null> (test_highs+0x7a5e2d)
    #8 ____C_A_T_C_H____T_E_S_T____0() <null> (test_highs+0x7a64b3)
    #9 Catch::TestInvokerAsFunction::invoke() const <null> (test_highs+0x7ce45d)
    #10 Catch::TestCase::invoke() const <null> (test_highs+0x7c6b43)
    #11 Catch::RunContext::invokeActiveTestCase() <null> (test_highs+0x7c6a68)
    #12 Catch::RunContext::runCurrentTest(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) <null> (test_highs+0x7c4b4b)
    #13 Catch::RunContext::runTest(Catch::TestCase const&) <null> (test_highs+0x7c4410)
    #14 Catch::(anonymous namespace)::TestGroup::execute() <null> (test_highs+0x7c9b1a)
    #15 Catch::Session::runInternal() <null> (test_highs+0x7c91b3)
    #16 Catch::Session::run() <null> (test_highs+0x7c902c)
    #17 int Catch::Session::run<char>(int, char const* const*) <null> (test_highs+0x7e3a93)
    #18 main <null> (test_highs+0x7e39f8)

SUMMARY: ThreadSanitizer: data race in std::enable_if<__and_<std::__not_<std::__is_tuple_like<HighsTaskExecutor*> >, std::is_move_constructible<HighsTaskExecutor*>, std::is_move_assignable<HighsTaskExecutor*> >::value, void>::type std::swap<HighsTaskExecutor*>(HighsTaskExecutor*&, HighsTaskExecutor*&)
==================
==================
WARNING: ThreadSanitizer: data race (pid=1216756)
  Write of size 8 at 0x7f013fa76320 by main thread:
    #0 std::__shared_count<(__gnu_cxx::_Lock_policy)2>::_M_swap(std::__shared_count<(__gnu_cxx::_Lock_policy)2>&) <null> (test_highs+0x7ebe27)
    #1 std::__shared_ptr<HighsTaskExecutor, (__gnu_cxx::_Lock_policy)2>::swap(std::__shared_ptr<HighsTaskExecutor, (__gnu_cxx::_Lock_policy)2>&) <null> (test_highs+0x8a3e13)
    #2 std::__shared_ptr<HighsTaskExecutor, (__gnu_cxx::_Lock_policy)2>::reset() <null> (test_highs+0x8a7e3d)
    #3 HighsTaskExecutor::shutdown(bool) <null> (test_highs+0x88e36c)
    #4 HighsTaskExecutor::ExecutorHandle::~ExecutorHandle() <null> (test_highs+0xadbc4d)
    #5 __call_tls_dtors /build/glibc-e6zv40/glibc-2.23/stdlib/cxa_thread_atexit_impl.c:155 (libc.so.6+0x3a60e)

  Previous read of size 8 at 0x7f013fa76320 by thread T5:
    [failed to restore the stack]

  Location is TLS of main thread.

  Thread T5 (tid=1216762, finished) created by main thread at:
    #0 pthread_create <null> (test_highs+0x760cdd)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xd0da4)
    #2 HighsTaskExecutor::HighsTaskExecutor(int) <null> (test_highs+0x89c4c2)
    #3 std::shared_ptr<HighsTaskExecutor> highs::cache_aligned::make_shared<HighsTaskExecutor, int&>(int&) <null> (test_highs+0x89c123)
    #4 HighsTaskExecutor::initialize(int) <null> (test_highs+0x89c012)
    #5 highs::parallel::initialize_scheduler(int) <null> (test_highs+0x881f66)
    #6 Highs::run() <null> (test_highs+0x882673)
    #7 highs_solve_simple_lp() <null> (test_highs+0x7a5e2d)
    #8 ____C_A_T_C_H____T_E_S_T____0() <null> (test_highs+0x7a64b3)
    #9 Catch::TestInvokerAsFunction::invoke() const <null> (test_highs+0x7ce45d)
    #10 Catch::TestCase::invoke() const <null> (test_highs+0x7c6b43)
    #11 Catch::RunContext::invokeActiveTestCase() <null> (test_highs+0x7c6a68)
    #12 Catch::RunContext::runCurrentTest(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) <null> (test_highs+0x7c4b4b)
    #13 Catch::RunContext::runTest(Catch::TestCase const&) <null> (test_highs+0x7c4410)
    #14 Catch::(anonymous namespace)::TestGroup::execute() <null> (test_highs+0x7c9b1a)
    #15 Catch::Session::runInternal() <null> (test_highs+0x7c91b3)
    #16 Catch::Session::run() <null> (test_highs+0x7c902c)
    #17 int Catch::Session::run<char>(int, char const* const*) <null> (test_highs+0x7e3a93)
    #18 main <null> (test_highs+0x7e39f8)

SUMMARY: ThreadSanitizer: data race in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::_M_swap(std::__shared_count<(__gnu_cxx::_Lock_policy)2>&)
==================
ThreadSanitizer: reported 3 warnings

jacobnzw avatar Oct 14 '22 22:10 jacobnzw

Is this master or latest release?

I can only say, that i had issues related to HighsTaskExecutor (serial code but repeated invocation) using current release which disappeared after going for master.

sschnug avatar Oct 14 '22 22:10 sschnug

I'm working with

rev: 4fbd2b93f182498dd596e0920eb87d10f4c37e17
Date:   Fri Jul 29 23:24:00 2022 +0100

I'll try with the latest master and report back.

jacobnzw avatar Oct 17 '22 07:10 jacobnzw

All I can say is that the multitasking environment (not written by me, I should add) was WIP for most of 2022, so it's quite possible that this race condition has been eliminated

jajhall avatar Oct 17 '22 21:10 jajhall

I've tried running TSAN on the latest master and I no longer see the same data races. However, there are still some. Here is a sample.

WARNING: ThreadSanitizer: data race (pid=59)
  Write of size 8 at 0x7b4000000480 by thread T27:
    #0 operator delete(void*) <null> (test_highs+0x5531c4)
    #1 void std::_Destroy_aux<false>::__destroy<std::unique_ptr<HighsSplitDeque, highs::cache_aligned::Deleter<HighsSplitDeque> >*>(std::unique_ptr<HighsSplitDeque, highs::cache_aligned::Deleter<HighsSplitDeque> >*, std::unique_ptr<HighsSplitDeque, highs::cache_aligned::Deleter<HighsSplitDeque> >*) <null> (test_highs+0x65cd62)

  Previous atomic read of size 1 at 0x7b4000000480 by thread T3:
    #0 pthread_mutex_lock <null> (test_highs+0x500af7)
    #1 HighsBinarySemaphore::acquire() <null> (test_highs+0x65d93f)

  Thread T27 (tid=87, running) created by main thread at:
    #0 pthread_create <null> (test_highs+0x50fe4d)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xd0da4)
    #2 ____C_A_T_C_H____T_E_S_T____0() <null> (test_highs+0x555553)
    #3 Catch::TestInvokerAsFunction::invoke() const <null> (test_highs+0x57d4fd)
    #4 Catch::TestCase::invoke() const <null> (test_highs+0x575be3)
    #5 Catch::RunContext::invokeActiveTestCase() <null> (test_highs+0x575b08)
    #6 Catch::RunContext::runCurrentTest(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) <null> (test_highs+0x573beb)
    #7 Catch::RunContext::runTest(Catch::TestCase const&) <null> (test_highs+0x5734b0)
    #8 Catch::(anonymous namespace)::TestGroup::execute() <null> (test_highs+0x578bba)
    #9 Catch::Session::runInternal() <null> (test_highs+0x578253)
    #10 Catch::Session::run() <null> (test_highs+0x5780cc)
    #11 int Catch::Session::run<char>(int, char const* const*) <null> (test_highs+0x592b33)
    #12 main <null> (test_highs+0x592a98)

  Thread T3 (tid=63, finished) created by main thread at:
    #0 pthread_create <null> (test_highs+0x50fe4d)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xd0da4)
    #2 ____C_A_T_C_H____T_E_S_T____0() <null> (test_highs+0x555553)
    #3 Catch::TestInvokerAsFunction::invoke() const <null> (test_highs+0x57d4fd)
    #4 Catch::TestCase::invoke() const <null> (test_highs+0x575be3)
    #5 Catch::RunContext::invokeActiveTestCase() <null> (test_highs+0x575b08)
    #6 Catch::RunContext::runCurrentTest(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) <null> (test_highs+0x573beb)
    #7 Catch::RunContext::runTest(Catch::TestCase const&) <null> (test_highs+0x5734b0)
    #8 Catch::(anonymous namespace)::TestGroup::execute() <null> (test_highs+0x578bba)
    #9 Catch::Session::runInternal() <null> (test_highs+0x578253)
    #10 Catch::Session::run() <null> (test_highs+0x5780cc)
    #11 int Catch::Session::run<char>(int, char const* const*) <null> (test_highs+0x592b33)
    #12 main <null> (test_highs+0x592a98)

SUMMARY: ThreadSanitizer: data race in operator delete(void*)

I wonder if highs.setOptionValue("parallel", "off") might get around this. In the release rev., I was getting the same tsan reports regardless.

jacobnzw avatar Oct 19 '22 08:10 jacobnzw

Another super odd thing is that, I seem to be getting these warnings only on this simple test case. When I compile my main target (the application of the lib to my problem, where I do have a call to highs.run()), none of these data races are reported.

jacobnzw avatar Oct 19 '22 08:10 jacobnzw