Bug 71780 - std::map::operator[] crashes with std::vector of objects used as key
Summary: std::map::operator[] crashes with std::vector of objects used as key
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.1.2
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2016-07-06 17:06 UTC by Kevin Harer
Modified: 2016-07-07 00:29 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments
The main.ii file to reproduce the problem (103.36 KB, text/plain)
2016-07-06 17:06 UTC, Kevin Harer
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Kevin Harer 2016-07-06 17:06:30 UTC
Created attachment 38841 [details]
The main.ii file to reproduce the problem

I have a crash when using std::map using a std::vector of small
objects.  When I use std::map::operator[] to insert new/unique values, 
it crashes after about 120 inserts - the larger application
crashes after >9000 inserts.  

When I use std::map::insert(std::pair<>()) it works like a champ.

I have reproduced it with a very simple testcase (below).
My system is ancient redhat linux:

gto[111]: g++ -v
Using built-in specs.
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-libgcj-multifile --enable-languages=c,c++,objc,obj-c++,java,fortran,ada --enable-java-awt=gtk --disable-dssi --disable-plugin --with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre --with-cpu=generic --host=x86_64-redhat-linux
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-52)
gto[119]: 

I have had friends at other companies that reproduced the issue 
with later versions (4.4.7, 4.8.4, and 6.1.0).  Since I dont have access 
and complete information I am reporting with my ancient setup.
One friend reports that the test does not crash on Apple.  He reports:

>> crashes on: g++ (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
>> succeeds on: Apple LLVM version 7.3.0 (clang-703.0.31)


I build and run the test using:

gto[119]: g++ -o crash -g -Wall -Wextra main.cc
main.cc:66: warning: unused parameter 'argc'
main.cc:66: warning: unused parameter 'argv'
gto[120]: crash
Hello world!
Generating 20K random Vecs and putting into the map:
Segmentation fault

I have attached the main.ii file.  The complete/small source 
file (main.cc) is below - it includes 3 std c++ header
files (map, vector, and iostream).  When I use
operator[] to insert unique key/value into the map, it crashes
after a hundred or so insertions.  (the real application
crashed after 9096 unique inserts).

      aMap[aVec] = val;  // this crashes eventually
      // aMap.insert ( std::pair<SmallVec, int>(aVec,val) );  // this always works
 
Feel free to contact me directly if that will help - 
Kevin Harer
kevin_harer@mentor.com
503-685-1306

Thank you -

/////////////////  main.cc   ///////////////////
#include <iostream>
#include <vector>
#include <map>


class Small {
public: // everything
  Small() {}
  ~Small() {}
  
  bool operator<(const Small &rhs) const;
  int _field1;
  int _field2;
  int _field3;
};

bool Small::operator<(const Small &rhs) const
{
  if (_field1 < rhs._field1) return(true);
  if (_field2 < rhs._field2) return(true);
  if (_field3 < rhs._field3) return(true);
  return(false);
}

typedef std::vector<Small> SmallVec;

static void
doExperiment()
{

  std::map<SmallVec, int> aMap;
  
  srand(27);
  std::cout << "Generating 20K random Vecs and putting into the map:" << std::endl;
  for (int i=0; i<20000;i++) {
    SmallVec aVec(5);
    int nEntry = rand() % 4 + 1; // range of path depth is 1 to 5
    // range of fields is  1 to 50
    for (int j=0;j<nEntry;j++) {
      Small sEnt;
      sEnt._field1 = rand()%50 + 1;
      sEnt._field2 = rand()%50 + 1;
      sEnt._field3 = rand()%50 + 1;
      aVec.push_back(sEnt);
    }
    int val;
    std::map<SmallVec, int>::iterator mapI = aMap.find(aVec);
    if (mapI == aMap.end()) {
      val = aMap.size();
      val++;
      aMap[aVec] = val;
      // aMap.insert ( std::pair<SmallVec, int>(aVec,val) );
    } else {
      val = mapI->second;
    }
  }


  return;
}

int
main(int argc, char **argv)
{
  std::cout << "Hello world!" << std::endl;
  doExperiment();
  return(0);
}
Comment 1 Daniel Krügler 2016-07-06 18:36:48 UTC
I can reproduce the problem for gcc versions smaller than 4.7.3, but I doubt that these old versions will be maintained for a fix.
Comment 2 Kevin Harer 2016-07-06 18:40:41 UTC
(In reply to Daniel Krügler from comment #1)
> I can reproduce the problem for gcc versions smaller than 4.7.3, but I doubt
> that these old versions will be maintained for a fix.

Daniel I sort of thought that - There is several acceptable work-arounds.
I just wanted to report it so it gets fixed wherever you can fix it -

Also - depending on the fix, I am not above hacking our own version
of headers...
Comment 3 Jonathan Wakely 2016-07-07 00:07:21 UTC
bool Small::operator<(const Small &rhs) const
{
  if (_field1 < rhs._field1) return(true);
  if (_field2 < rhs._field2) return(true);
  if (_field3 < rhs._field3) return(true);
  return(false);
}

This is not a valid StrictWeakOrdering, so it's undefined behaviour to put those objects into a std::map. This is a bug in your code, not GCC.

Consider:

#include <cassert>

class Small {
public:
  Small() {}
  ~Small() {}

  bool operator<(const Small &rhs) const;
  int _field1;
  int _field2;
  int _field3;
};

bool Small::operator<(const Small &rhs) const
{
  if (_field1 < rhs._field1) return(true);
  if (_field2 < rhs._field2) return(true);
  if (_field3 < rhs._field3) return(true);
  return(false);
}

int
main()
{
  Small a, b;
  a._field1 = 1;
  a._field2 = 2;
  a._field3 = 0;
  b._field1 = 2;
  b._field2 = 1;
  b._field3 = 0;

  assert( ! ((a < b) && (b < a)) );
}

The assertion fails.

https://www.sgi.com/tech/stl/StrictWeakOrdering.html
Comment 4 Jonathan Wakely 2016-07-07 00:14:34 UTC
N.B. it doesn't matter that you're using map<vector<Small>, int> rather than map<Small, int> directly, because the comparisons on the vector use the comparisons on the Small type, so an invalid ordering for Small produces an invalid ordering for SmallVec too.

This still fails:

  std::vector<Small> va(1, a), vb(1, b);
  assert( ! ((va < vb) && (vb < va)) );
Comment 5 Kevin Harer 2016-07-07 00:29:44 UTC
Well darn.  You are right.  I am sorry for wasting your time - but glad that
I did, in that the error will come out in my application in some other
worse way -

Thank you for your time -