get double corruption error when trying to reallocate dynamic arrays

Question

There is a piece of code:

    #include <iostream>
    #include <cstring>

    using std::cout, std::endl;

    struct Chunk{
      Chunk(){}
      int* get(){ return reinterpret_cast<int*>(&_data[0]);}
      unsigned char _data[sizeof(int)];
    };

    class MemoryPool{
    public:
      MemoryPool(size_t capacity):_capacity(capacity)
      {
        _size=0;
        _data=new Chunk[_capacity];
        _vacant=new bool[_capacity];
        for(int i=0; i<_capacity; ++i) _vacant[i]=true;
      }
      ~MemoryPool()
      {
        delete [] _data;
        delete [] _vacant;
      }
      size_t size() const {return _size;}
      size_t capacity() const {return _capacity;}
      int* allocate()
      {
        int index=find_vacant();
        if(-1 == index)
        {
          reallocate();
          index=find_vacant();
        }
        _vacant[index]=false;
        ++_size;
        return get(index);
      }
      void reallocate()
      {
        const int new_capacity=2*_capacity+1;
        Chunk* new_data  =new Chunk[new_capacity];
        bool*  new_vacant=new bool[new_capacity];
        std::memcpy(new_data, _data, _size*sizeof(Chunk));
        std::memcpy(new_vacant, _vacant, _size*sizeof(bool));
        for(int i=_size; i<new_capacity; ++i) new_vacant[i]=true;
        std::swap(_data,new_data);
        std::swap(_vacant,new_vacant);
        delete [] new_data;
        delete [] new_vacant;
        _capacity=new_capacity;
      }  
      int* get(int index)
      {
        return reinterpret_cast<int*>(&_data[index]);
      }
      int find_vacant()
      {
        int index=-1;
        for(int i=0; i<(int)_capacity; ++i)
        {
          if(_vacant[i])
          {
            index=i;
            break;
          }
        }
        return index;
      }  
    private:
      size_t _size;
      size_t _capacity;
      Chunk* _data;
      bool* _vacant;
    };

    int main()
    {
      MemoryPool pool(10);
      cout<<"pool.size()="<<pool.size()<<endl;
      for(int i=0; i<11; ++i)
      {
        int* ptr=pool.allocate();
        *ptr=i+1;
      }
      cout<<"PRINT:"<<endl;
      for(int i=0; i<pool.size(); ++i) cout<<*(pool.get(i))<<" ";
      cout<<endl;
      return 0;
    }

The code fails at the end of runtime with a double corruption error:

    double free or corruption (out)
    Aborted (core dumped)

The error occurs in the destructor ~MemoryPool() when calling delete [] operators for the pointers pointing to the arrays. I tried to use

   valgrind --tool=memcheck ./a.out

It points to the reallocate() function, but I can't understand the output of valgrind.

Of course, I know that it is not recommended to work with dynamic memory allocation directly and strongly recommended to use STL containers.

As for my question, it must be some silly error, but I can't understand what I'm doing wrong. It seemes to me that I allocate and delete the dynamic arrays properly.

Answer 1

Your problem is that you do not set the new_vacant array up correctly. In the constructor you have a small loop that ensures that all spaces in your MemoryPool are vacant:

for (size_t i = 0; i < _capacity; ++i)
    _vacant[i] = true;

This loop is missing in reallocate().

Why does this matter? Because right after calling reallocate() you call index = find_vacant(), and then you straight up use that index _vacant[index] = false and *ptr = i + 1.

However, since your entire array is marked as "used up" you are getting index -1. Which again means that you are writing into _vacant[-1] and _data[-1] - I hope you see the problem.

Also, I think (very not sure, may also be implementation defined) that new uses some of the space "in front" of the chunk you get to place allocation information into (stuff like number of elements etc.) - so that may be what you are overwriting here.