Search code examples
c++sortingsegmentation-faultstdlist

Segmentation Fault on std::list::sort with custom comparator?

In some code I have a linked list with objects of type PlayerObject

std::list<PlayerObject> unknownPlayers;

And I need to sort the objects according to some property, so I use the class

class CountCmp
    : public std::binary_function< PlayerObject, PlayerObject, bool >
{
public:
    result_type operator()( const first_argument_type & lhs,
                            const second_argument_type & rhs ) const
      {
         return lhs.posCount() < rhs.posCount();
      }
};

By

unknownPlayers.sort( PlayerObject::CountCmp() );

But for some reason the program is receiving SEGV. I used -fsanitize=address compilation flag to investigate and the stack-trace was like:

ASAN:SIGSEGV
=================================================================
==8521==ERROR: AddressSanitizer: SEGV on unknown address 0x0003000003e8 (pc 0x7fe7ca6d6540 bp 0x7fff07c51720 sp 0x7fff07c516e8 T0)
#0 0x7fe7ca6d653f in std::__detail::_List_node_base::_M_transfer(std::__detail::_List_node_base*, std::__detail::_List_node_base*) (/usr/lib/x86_64-linux-gnu/libstdc++.so.6+0x9e53f)
#1 0x881e58 in std::__cxx11::list<rcsc::PlayerObject, std::allocator<rcsc::PlayerObject> >::_M_transfer(std::_List_iterator<rcsc::PlayerObject>, std::_List_iterator<rcsc::PlayerObject>, std::_List_iterator<rcsc::PlayerObject>) /usr/include/c++/5/bits/stl_list.h:1747
#2 0x87f79f in std::__cxx11::list<rcsc::PlayerObject, std::allocator<rcsc::PlayerObject> >::splice(std::_List_const_iterator<rcsc::PlayerObject>, std::__cxx11::list<rcsc::PlayerObject, std::allocator<rcsc::PlayerObject> >&&, std::_List_const_iterator<rcsc::PlayerObject>) /usr/include/c++/5/bits/stl_list.h:1444
#3 0x87d22e in std::__cxx11::list<rcsc::PlayerObject, std::allocator<rcsc::PlayerObject> >::splice(std::_List_const_iterator<rcsc::PlayerObject>, std::__cxx11::list<rcsc::PlayerObject, std::allocator<rcsc::PlayerObject> >&, std::_List_const_iterator<rcsc::PlayerObject>) /usr/include/c++/5/bits/stl_list.h:1464
#4 0x87d90c in void std::__cxx11::list<rcsc::PlayerObject, std::allocator<rcsc::PlayerObject> >::sort<rcsc::PlayerObject::CountCmp>(rcsc::PlayerObject::CountCmp) (/home/felipe_coimbra/.../sample_player+0x87d90c)
#5 0x86c3e3 in rcsc::WorldModel::localizePlayers(rcsc::VisualSensor const&) /home/felipe_coimbra/.../world_model.cpp:2412
#6 0x864b37 in rcsc::WorldModel::updateAfterSee(rcsc::VisualSensor const&, rcsc::BodySensor const&, rcsc::ActionEffector const&, rcsc::GameTime const&) /home/felipe_coimbra/.../world_model.cpp:910
#7 0x81a7ac in rcsc::PlayerAgent::Impl::analyzeSee(char const*) /home/felipe_coimbra/.../player_agent.cpp:1552
#8 0x819b52 in rcsc::PlayerAgent::parse(char const*) /home/felipe_coimbra/.../player_agent.cpp:1393
#9 0x816519 in rcsc::PlayerAgent::handleMessage() /home/felipe_coimbra/.../player_agent.cpp:886
#10 0x75b3a8 in rcsc::BasicClient::runOnline(rcsc::SoccerAgent*) /home/felipe_coimbra/.../basic_client.cpp:158
#11 0x75ac9e in rcsc::BasicClient::run(rcsc::SoccerAgent*) /home/felipe_coimbra/.../basic_client.cpp:93
#12 0x5e933e in main /home/felipe_coimbra/.../main_player.cpp:102
#13 0x7fe7c9d6f82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#14 0x5e8ed8 in _start (/home/felipe_coimbra/.../sample_player+0x5e8ed8)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV ??:0      std::__detail::_List_node_base::_M_transfer(std::__detail::_List_node_base*, std::__detail::_List_node_base*)
==8521==ABORTING

It seems to me the comparator is ok for strict-weak ordering. So what would be other possible cause to a segmentation fault in std::list::sort ?

EDIT 1:

I've tried to tranverse unknownPlayers using list::iterator and list::reverse_iterator just before sorting and it works fine. I could even access values through posCount() method and there wasn't anything odd with the returned values.

EDIT 2:

I've been trying to pick relevant code to post but I'm finding it a little troublesome. I think some relevant facts about unknownPlayers would be:

  1. It's filled by std::list::splice method:

    unknownPlayers.splice(unknownPlayers.end(), new_unknown_players );

new_unknown_players is also filled by splice. Basically in every game cycle there's new information about seen players and these players may be identified as teammates, opponents or not identified at all(unknown players). There is a try to match not identified players with previously identified players(teammates or opponents) by a proximity threshold and if this fails, they're spliced into new_unknown_players linked list.

  1. sort also does crash in the same way if I try to sort unknownPlayers before the call of splice in the line of code above

  2. However, sort does not crash while unknownPlayers is empty (thank god it's not that messed up) and right after the first time the splice actually adds new objects and makes it not-empty for the first time.

Maybe this means in some other part of code something is corrupting the list? I can't still understand why tranversing is ok.

Code of this part:

//////////////////////////////////////////////////////////////////
// splice temporary seen players to memory list
// temporary lists are cleared
M_teammates.splice(M_teammates.end(),
                       new_teammates);
M_opponents.splice(M_opponents.end(),
                       new_opponents);
// I've put some debug in this line
M_unknown_players.splice(M_unknown_players.end(),
                             new_unknown_players);
// And here too

/////////////////////////////////////////////////////////////////
    // create team member pointer vector for sort

    PlayerPtrCont all_teammates_ptr;
    PlayerPtrCont all_opponents_ptr;

    {
        const PlayerCont::iterator end = M_teammates.end();
        for (PlayerCont::iterator it = M_teammates.begin();
             it != end;
             ++it) {
            all_teammates_ptr.push_back(&(*it));
        }
    }
    {
        const PlayerCont::iterator end = M_opponents.end();
        for (PlayerCont::iterator it = M_opponents.begin();
             it != end;
             ++it) {
            all_opponents_ptr.push_back(&(*it));
        }
    }

/////////////////////////////////////////////////////////////////
    // sort by accuracy count
    std::sort(all_teammates_ptr.begin(),
              all_teammates_ptr.end(),
              PlayerObject::PtrCountCmp());
    std::sort(all_opponents_ptr.begin(),
              all_opponents_ptr.end(),
              PlayerObject::PtrCountCmp());

// I've put some more debug here
M_unknown_players.sort( PlayerObject::CountCmp() );
// And here
Solution

  • Well, thing is I ended up solving the issue myself.

    Apparently that was a collateral effect of a huge collection of bugs. And when I say huge I mean dozens. Undefined behavior is a true pain in the ass.

    It's a pitty that sanitizers and softwares like Valgrind are unable to te identify properly what code is corrupting stack memory sometimes. The sort function was just accessing an already corrupted linked list in this case. Wonder If there's any more precise/detailed tools for this.

    Anyway, thank you all.