Segmentation fault when I call operator new in linux mint

Question

On Linux Mint, I use operator new to alloc memory:

int maxNummber = 1000000;
int* arr = new int[maxNumber];

when I run my code, I meet

flybird@flybird ~/cplusplus_study $ ./a.out 
-412179
Segmentation fault

when I change maxNumber = 100, the code runs successfully.

the result of command free -m:

flybird@flybird ~/cplusplus_study $ free -m
              total       used       free     shared    buffers     cached
Mem:          2016        800       1216          0        158        359
-/+ buffers/cache:        283       1733
Swap:         2045          0       2045

---

This is the actual code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <fstream>
#include <ctime>
#include <memory>
#include <string.h>
#include <iterator>
#include <cstdlib>
using namespace std;

class GenRandomNumber;

class BitMap
{
public:
    BitMap(int n):maxNumer(n)
    {
        int length = 1 + n / BITSPERWORD;
        pData = new int[length];
        memset(pData, 0, length);
    }
    void set(int i)
    {
        pData[i>>SHIFT] |= 1<<(i & MASK); // i&MASK 相当于i%32
    }
    void clear(int i)
    {
        pData[i>>SHIFT] &= ~(1<<(i & MASK)); // i>>SHIFT 相当于 i/32
    }
    bool test(int i)
    {
        return pData[i>>SHIFT] & (1<<(i & MASK));
    }

    void sort(string inputFile, string outputFile)
    {
        ifstream read(inputFile.c_str());
        ofstream write(outputFile.c_str());
        int temp = 0;

        while (read>>temp)
            set(temp);

        for (int i = 0; i < maxNumer; ++i)
        {
            if(test(i))
                write<<i<<endl;
        }
        read.close();
        write.close();
    }
    ~BitMap()
    {
        delete []pData;
        pData = NULL;
    }
private:
    int* pData;
    int maxNumer;
    enum{ SHIFT = 5, MASK = 0x1F, BITSPERWORD = 32};
};

class GenRandomNumber
{
public:
    static GenRandomNumber* genInstance()
    {
        if(!mInstance.get())
            mInstance.reset(new GenRandomNumber());
        return mInstance.get();
    }

    void generate1(string fileName, int m, int maxNumber)
    {
        ofstream outFile(fileName.c_str());
        int* arr = new int[maxNumber];
        for(int i = 0; i < maxNumber; i++)
            arr[i] = i;

        int temp = 0;
        for(int j = 0; j < m; j++)
        {
            temp = randomRange(j, maxNumber - 1);
            cout<<temp<<endl;
            swap(arr[j], arr[temp]);
        }

        copy(arr, arr + m, ostream_iterator<int>(outFile, "\n"));
        delete []arr;
        outFile.close();
    }

    void generate2(string fileName, int m, int maxNumber)
    {
        BitMap bitmap(maxNumber);
        ofstream outFile(fileName.c_str());
        int count = 0;
        int temp;
        while (count < m)
        {
            srand(time(NULL));
            temp = randomRange(0, maxNumber);
            cout<<temp<<endl;
            if (!bitmap.test(temp))
            {
                bitmap.set(temp);
                outFile<<temp<<endl;
                count++;
            }
        }
        outFile.close();
    }
private:
    GenRandomNumber(){};
    GenRandomNumber(const GenRandomNumber&);
    GenRandomNumber& operator=(const GenRandomNumber&);

    int randomRange(int low, int high)
    {
        srand(clock()); // better than srand(time(NULL))
        return low + (RAND_MAX * rand() + rand()) % (high + 1 - low);;
    }

    static auto_ptr<GenRandomNumber> mInstance;
};
auto_ptr<GenRandomNumber> GenRandomNumber::mInstance;



int main()
{
    const int MAX_NUMBER = 1000000;
    GenRandomNumber *pGen = GenRandomNumber::genInstance();
    pGen->generate1("test.txt", MAX_NUMBER, MAX_NUMBER);
    BitMap bitmap(MAX_NUMBER);
    bitmap.sort("test.txt", "sort.txt");
    return 0;
}

Answer 1

There is one problem in the code may not directly explain the segment fault, but should also draw your attention. Note that In the class BitMap, the constructor:

BitMap(int n):maxNumer(n)
{
    int length = 1 + n / BITSPERWORD;
    pData = new int[length];
    memset(pData, 0, length);
}

The third parameter of memset is meant to be the size of allocated array, not number of elements, so it should be:

BitMap(int n):maxNumer(n)
{
    int length = 1 + n / BITSPERWORD;
    pData = new int[length];
    memset(pData, 0, length * sizeof(int));
}

The original code might causes problem because only part of the allocated array is initialized to zero by memset. The remaining code might be logically wrong because class BitMap do binary operator in the member function (set, clear, test), in which all of them presume all elements of the array that pData pointed to are set to be zero.

Answer 2

Here's one of the problems. m is too large and exceeds maxNumber. arr[j], when j=m, exceeds the its bounds because arr is only maxNumber in size. See the info on stack frame #1: m=1606416912, maxNumber=999999.

By the way, a well placed assert would have alerted you to this problem (I'm a big fan of self debugging code - I hate spending time under the debugger):

void generate1(string fileName, int m, int maxNumber)
{
  assert(!fileName.empty());
  assert(m > 0 && maxNumber > 0);
  assert(m <= maxNumber);
  ...
}

And the back trace:

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x000000010007eef8
std::swap<int> (__a=@0x100200000, __b=@0x10007eef8) at stl_algobase.h:99
99        __a = __b;
(gdb) bt full
#0  std::swap<int> (__a=@0x100200000, __b=@0x10007eef8) at stl_algobase.h:99
    __tmp = 0
#1  0x0000000100000ff1 in GenRandomNumber::generate1 (this=0x7fff5fbffa10, fileName=@0x100200000, m=1606416912, maxNumber=999999) at t.cpp:91
    outFile = {
  <std::basic_ostream<char,std::char_traits<char> >> = {
    <std::basic_ios<char,std::char_traits<char> >> = {
      <std::ios_base> = {
        _vptr$ios_base = 0x7fff745bc350, 
        _M_precision = 6, 
        _M_width = 0, 
        _M_flags = 4098, 
        _M_exception = std::_S_goodbit, 
        _M_streambuf_state = std::_S_goodbit, 
        _M_callbacks = 0x0, 
        _M_word_zero = {
          _M_pword = 0x0, 
          _M_iword = 0
        }, 
        _M_local_word = {{
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }, {
            _M_pword = 0x0, 
            _M_iword = 0
          }}, 
        _M_word_size = 8, 
        _M_word = 0x7fff5fbff910, 
        _M_ios_locale = {
          _M_impl = 0x7fff745c1880
        }
      }, 
      members of std::basic_ios<char,std::char_traits<char> >: 
      _M_tie = 0x0, 
      _M_fill = 0 '\0', 
      _M_fill_init = false, 
      _M_streambuf = 0x7fff5fbff660, 
      _M_ctype = 0x7fff745c1ab0, 
      _M_num_put = 0x7fff745c1dd0, 
      _M_num_get = 0x7fff745c1dc0
    }, 
    members of std::basic_ostream<char,std::char_traits<char> >: 
    _vptr$basic_ostream = 0x7fff745bc328
  }, 
  members of std::basic_ofstream<char,std::char_traits<char> >: 
  _M_filebuf = {
    <std::basic_streambuf<char,std::char_traits<char> >> = {
      _vptr$basic_streambuf = 0x7fff745bc230, 
      _M_in_beg = 0x100803200 "", 
      _M_in_cur = 0x100803200 "", 
      _M_in_end = 0x100803200 "", 
      _M_out_beg = 0x0, 
      _M_out_cur = 0x0, 
      _M_out_end = 0x0, 
      _M_buf_locale = {
        _M_impl = 0x7fff745c1880
      }
    }, 
    members of std::basic_filebuf<char,std::char_traits<char> >: 
    _M_lock = {
      __sig = 0, 
      __opaque = '\0' <repeats 55 times>
    }, 
    _M_file = {
      _M_cfile = 0x7fff756bf0a0, 
      _M_cfile_created = true
    }, 
    _M_mode = 48, 
    _M_state_beg = {
      __mbstate8 = '\0' <repeats 127 times>, 
      _mbstateL = 0
    }, 
    _M_state_cur = {
      __mbstate8 = '\0' <repeats 127 times>, 
      _mbstateL = 0
    }, 
    _M_state_last = {
      __mbstate8 = '\0' <repeats 127 times>, 
      _mbstateL = 0
    }, 
    _M_buf = 0x100803200 "", 
    _M_buf_size = 1024, 
    _M_buf_allocated = true, 
    _M_reading = false, 
    _M_writing = false, 
    _M_pback = 0 '\0', 
    _M_pback_cur_save = 0x0, 
    _M_pback_end_save = 0x0, 
    _M_pback_init = false, 
    _M_codecvt = 0x7fff745c1cf0, 
    _M_ext_buf = 0x0, 
    _M_ext_buf_size = 0, 
    _M_ext_next = 0x0, 
    _M_ext_end = 0x0
  }
}
#2  0x0000000100000a18 in main () at t.cpp:140
    bitmap = {
  pData = 0x7fff5fc005a8, 
  maxNumer = 17
}
    pGen = (GenRandomNumber *) 0x1001000e0

Answer 3

gdb already gave you a hint where the error is coming from. The only place where you use swap is in this function:

void generate1(string fileName, int m, int maxNumber)
{
    ofstream outFile(fileName);
    int* arr = new int[maxNumber];
    for(int i = 0; i < maxNumber; i++)
        arr[i] = i;

    int temp = 0;
    for(int j = 0; j < m; j++)
    {
        temp = randomRange(j, maxNumber - 1);
        cout<<temp<<endl;
        swap(arr[j], arr[temp]); // <----
    }

    copy(arr, arr + m, ostream_iterator<int>(outFile, "\n"));
    delete []arr;
    outFile.close();
}

Swapping two ints isn't likely to be the culprit, unless you give it invalid input to begin with. arr[j] is pretty straightforward and should be fine, but what about arr[temp]? temp is calculated here:

temp = randomRange(j, maxNumber - 1);

and randomRange function looks like this:

int randomRange(int low, int high)
{
    srand(clock()); // better than srand(time(NULL))
    return low + (RAND_MAX * rand() + rand()) % (high + 1 - low);;
}

I'd say this is your problem. RAND_MAX * rand() probably overflows and gives you big negative numbers. Hopefully it's obvious why that's not good.

Answer 4

The problem is in your randomRange function.

return low + (RAND_MAX * rand() + rand()) % (high + 1 - low);;

I don't know, why do you multiple (RAND_MAX + 1) by rand()(which return value between 0 and RAND_MAX), but it causes overflow and may be negative.

If C++11 is an option for you, I can suggest use uniform_int_distribution. It will return a number between passed min and max values.

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 6);

    for (int n=0; n<10; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

Answer 5

1,000,000 probably should not fail on a modern desktop, so I expect you are blowing up elsewhere.

To see what/where the problem is:

$ gdb
gdb> file ./a.out
gdb> run
<wait for crash>
gdb> bt full

If the allocation failed, you should see an uncaught bad_alloc exception.

Otherwise, please post the source code and results of the backtrace.