allocator<T>::allocate(1) returns <Bad Ptr>

[jetimms]

I am working on getting a program for Accelerated C++ (Koenig and Moo), chapter 11 running against earlier examples in the book.

The following method's intent is to add allocated room into my container. It is not necessarily the first place the memory gets allocated.

data: is the first address in my container
avail: is the first address past the last one containing a valid object
limit: one step past the last byte of allocated space

as such:

|data|avail  |limit
|used|notused|
| allocated  |

From ch 11.5.1, p.208

  typedef T* iterator;
  typdef size_t size_type;
  std::allocator<T> alloc;

  template <typename T> void Vec<T>::grow()
  {
    size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = std::uninitialized_copy(data, avail, new_data);

    uncreate();

    data = new_data;
    avail = new_avail;
    limit = data + new_size;
  }

This method successfully runs when the container has already been allocated. However when limit and avail equal zero, alloc.allocate() gets ptrdiff_t(1) and returns a <Bad Ptr>.

I am running this against the compiler that comes with the Visual Studio 2008 Command Prompt (I have no idea what version.)

I am also running it with the following compiler flags (if it makes a difference):

cl.exe /EHsc /GR /nologo /Zc:forScope /Zc:wchar_t ...

I get no compiler errors.

My question is, are there some idiosyncracies about the allocator<T> object that might cause it to return a <Bad Ptr> if fed a size_t of 1?

Thanks.

[Hammurabi]

Are you certain that max is returning 1 in the case you indicate? Almost certainly it isn't. Check that out. And you haven't mentioned if data is initialized to 0.

[PanGalactic]

There should not be a problem with that. You can verify yourself by injecting

iterator new_data = alloc.allocate(1);

into the code and checking that you got a good value back.

Are you sure that limit and data are both initialized to 0 at that point?

[jetimms]

Yes, data, avail and limit are all equal to zero at that point, in the case where it fails.

Therefore, the max above is returning 1 (again in this case only). I have found that where there is a difference between data and limit, allocate returns a valid address.

I did attempt to feed alloc.allocate() a 1 and sure enough it returned <Bad Ptr>.

Here is some more code to show you the lead up to the error:

from cat.cpp

int main() {
  Vec<string> firstWordsSplit, secondWordsSplit;

  cout << endl;
  cout << "Enter the first words: " << endl;
  string firstWords;
  if(getline(cin, firstWords))
  {
    firstWordsSplit = split(firstWords);
...

From split.cpp of ch 5.6, p.88

Vec<string> split(const string& s) {
  Vec<string> splitVector;
  typedef string::size_type string_size;
  string_size i = 0;

  // invariant: we have processed characters [original value of i, i]
  while (i != s.size()) {
    // ignore leading blanks
    // invariant: characters in range [original i, current j) are all spaces
    while (i != s.size() && isspace(s[i]))
      ++i;

    // find end of next word
    string_size j = i;
    // invariant: none of the characters in range [original j, current j) is a space
    while (j != s.size() && !isspace(s[j]))
      ++j;

    // if we found some nonwhitespace characters
    if (i != j) {
      // copy from s starting at i and taking j - i chars
      splitVector.push_back(s.substr(i, j - i));
...

from Vec.h

  template <typename T> class Vec
  {
    Vec<T>::create()
    {
      data = avail = limit = NULL;
    }
...
    void push_back(const T& val)
    {
      if (avail == limit)
      {
        grow();
...

I included the default constructor that's getting called in the case of firstWordsSplit and SplitVector. SplitVector is actually the one that receives the <Bad Ptr>.

Sorry I didn't clarify these things earlier.

[Hammurabi]

You call it a default constructor, but it is actually a member function called create. Are you sure it's getting called?

[jetimms]

You are correct. My mistake. Vec<T>::create() is the sole function that my default constructor calls. Actually I may be calling it the wrong thing, but in essense its the constructor with no parameters. I will confirm when I return home later tonight.

I am wondering if there's a problem (in regards to allocator) with the latest version of the VS 2008 compiler, or the headers/libraries that come with it.

I found the following in the Errata for Accelerate C++, for this very example.

http://www.acceleratedcpp.com/details/msbugs.html

I tried what is suggested here, but still get the error, even while providing the hint argument of zero.

[Hammurabi]

It occurs to me that this line may not be doing what you want.

iterator new_avail = std::uninitialized_copy(data, avail, new_data);

Just ignore uninitialized_copy's return value and calculate your new_avail:

iterator new_avail = new_data + (avail - data);

[jetimms]

I see you're point. I did not think about trying that and it could be another location I am getting a <Bad Ptr>, since new_avail does receive this value from uninitialized_copy.

However, even before uninitialized_copy is ran, new_data gets <Bad Ptr> from alloc.allocate(1).

On deeper inspection into the allocate method, I have found this:

from c:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\include\xmemory

// TEMPLATE CLASS _Allocator_base<const _Ty>
template<class _Ty>
struct _Allocator_base<const _Ty>
{	// base class for generic allocators for const _Ty
  typedef _Ty value_type;
};

// TEMPLATE CLASS allocator
template<class _Ty>
class allocator
  : public _Allocator_base<_Ty>
{	// generic allocator for objects of class _Ty
public:
...
  typedef value_type _FARQ *pointer;
...
pointer allocate(size_type _Count)
{	// allocate array of _Count elements
  return (_Allocate(_Count, (pointer)0));
}
...
pointer allocate(size_type _Count, const void _FARQ *)
{	// allocate array of _Count elements, ignore hint
  return (allocate(_Count));
}

Notice that alloc.allocate(size_type new_size, 0) calls allocate(size_type n) and ignores the hint!

The reason that this is disturbing is because the only function it can call is this:

from c:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\include\xmemory

// TEMPLATE FUNCTION _Allocate
template<class _Ty> inline
_Ty _FARQ *_Allocate(_SIZT _Count, _Ty _FARQ *)
{	// check for integer overflow
  if (_Count <= 0)
    _Count = 0;
  else if (((_SIZT)(-1) / _Count) < sizeof (_Ty))
    _THROW_NCEE(std::bad_alloc, NULL);

  // allocate storage for _Count elements of type _Ty
  return ((_Ty _FARQ *)::operator new(_Count * sizeof (_Ty)));
}

Here our size_t of 1 goes into _Count and (I think) the second argument (pointer)0 from allocate(size_t n) is provide so that the return type will be known.

Here the exception isn't getting thrown so ... I don't really know what that means about _SIZT, is it negative? (let's ignore that line :D)

Finally, we get to the final expressing where the return statement calls (string*)::new on 1 * sizeof(string)? That should work.

Not sure what's happening, but the final line here is where I am receiving the first <Bad Ptr>.

[Hammurabi]

_SIZT is presumably an unsigned long. (_SIZT)(-1) is therefore the highest value for an unsigned long. Dividing this number by the number of objects you want to allocate gives the maximum size that each object can be to fit into the address space. It's there to ensure that the calculation _Count * sizeof(_Ty) won't overflow. Exactly why they feel it necessary to check if _Count is negative is a mystery!

Can you see what _Count equals before that last line is executed? I bet it's a REALLY big number!

Have you checked that create() is being called properly from the constructor?

Try putting this in your code just before the line with std::max.
if( data > limit ) throw("yikes"); // or whatever

[jetimms]

Actually _Count is 1!

I tried the if/throw. It did not fire for the first variable, but who knows by the time the second one is allocated.

I added this to the xmemory header to get an idea of what was getting created:

  _SIZT sizt = -1;
  size_t tyvalue = sizeof(_Ty);

Like you said, _SIZT(-1) is 4294967295 (probs the biggest unsigned long) and sizeof(_Ty) is 32.

Now that I look at it, that return looks kind of funny.

  return ((_Ty _FARQ *)::operator new(_Count * sizeof (_Ty)));

Why would it return a new on the ::operator?

Btw: I never have understood what _FARQ is, or the usage of far/near.

[Hammurabi]

So _Count is 1. That would seem to eliminate the simpler possibilities.

I tried the if/throw. It did not fire for the first variable, but who knows by the time the second one is allocated.

I'm not sure what you mean by the second one.

_SIZT(-1) is 4294967295 (probs the biggest unsigned long) and sizeof(_Ty) is 32.

Yep, 4294967295 is the highest unsigned value (in 32 bits). 32 seems a little high for sizeof(_Ty). I would have thought 4, but whatever.

Why would it return a new on the ::operator?

Class::operator new is the name of the function for the new operator, just as Class::operator++ is the name of the function for the increment operator.

I never have understood what _FARQ is

_FARQ is probably a macro that disappears (evaluates to a space) on most systems. Let's allow it to do so in our minds.


At this juncture you will have to post your entire program. I'm assuming it is not that large. Post it and I'll test it on a different compiler.

BTW, if you change 1 to 10, does it work?

[jetimms]

Not sure why, but 10 didn't work either.

Here's the code (and probably on the next post as well.

cat.h

#ifndef GUARD_cat_h
#define GUARD_cat_h

#include <string>
#include "..\Vec.h"

Vec<std::string> hcat(
    const Vec<std::string>&,
    const Vec<std::string>&);

Vec<std::string> vcat(
    const Vec<std::string>&,
    const Vec<std::string>&);

#endif GUARD_cat_h 

from cat.cpp

#include <iostream>
#include <string>
#include "cat.h"
#include "frame.h"
#include "split.h"
#include "..\Vec.h"

using std::cin;
using std::cout;
using std::endl;
using std::string;

Vec<string> vcat(
    const Vec<string>& top,
    const Vec<string>& bottom) {

  Vec<string> joinedPictures = top;

  joinedPictures.insert(
    joinedPictures.end(),
    bottom.begin(),
    bottom.end());

  return joinedPictures;
}

Vec<string> hcat(
    const Vec<string>& left,
    const Vec<string>& right) {

  Vec<string> joinedPictures;
  
  string::size_type widthLeft = width(left) + 1;

  Vec<string>::size_type i = 0, j= 0;

  while (i != left.size() || j != right.size()) {
    string pictures;
    
    if (i != left.size())
      pictures = left[i++];

    pictures += string(widthLeft - pictures.size(), ' ');

    if (j != right.size())
      pictures += right[j++];

    joinedPictures.push_back(pictures);
  }

  return joinedPictures;
}

int main() {
  Vec<string> firstWordsSplit, secondWordsSplit;

  cout << endl;
  cout << "Enter the first words: " << endl;
  string firstWords;
  if(getline(cin, firstWords)) {
    firstWordsSplit = split(firstWords);
  }

  firstWordsSplit = frame(firstWordsSplit);

  cout << endl;
  cout << "Enter the second words: " << endl;
  string secondWords;
  if(getline(cin, secondWords)) {
    secondWordsSplit = split(secondWords);
  }

  secondWordsSplit = frame(secondWordsSplit);

  cout << "Vertical Concatenation: " << endl;
  Vec<string> verticalCat = vcat(firstWordsSplit, secondWordsSplit);

  for (Vec<string>::const_iterator vrow = verticalCat.begin();
      vrow != verticalCat.end(); ++vrow) {
    cout << (*vrow) << endl;
  }

  cout << "Horizontal Concatenation: " << endl;
  Vec<string> horizontalCat = hcat(firstWordsSplit, secondWordsSplit);

  for (Vec<string>::const_iterator hrow = horizontalCat.begin();
      hrow != horizontalCat.end(); ++hrow) {
    cout << (*hrow) << endl;
  }

  return 0;
}

from frame.h

#ifndef GUARD_frame_h
#define GUARD_frame_h

#include <string>
#include "..\Vec.h"

std::string::size_type width(const Vec<std::string>&);
Vec<std::string> frame(const Vec<std::string>&);

#endif GUARD_frame_h 

from frame.cpp

#include <string>
#include "frame.h"
#include "..\Vec.h"

using std::max;
using std::string;

string::size_type width(const Vec<string>& v) {
  string::size_type maxlen = 0;
  for(Vec<string>::size_type i = 0; i < v.size(); ++i) {
    maxlen = max(maxlen, v[i].size());
  }

  return maxlen;
}

Vec<string> frame(const Vec<string>& v)
{
  Vec<string> frameVector;
  string::size_type maxlen = width(v);
  string border(maxlen + 4, '*');

  // write the top border
  frameVector.push_back(border);

  // write each interior row, bordered by an asterisk and a space
  for (Vec<string>::size_type i = 0; i != v.size(); ++i) {
    frameVector.push_back(
        "* " + v[i] + string(maxlen - v[i].size(), ' ') + " *");
  }

  // write the bottom border
  frameVector.push_back(border);

  return frameVector;
}

from split.h

#ifndef GUARD_split_h
#define GUARD_split_h

#include <string>
#include "..\Vec.h"

Vec<std::string> split(const std::string&);

#endif GUARD_split_h 

from split.cpp

#include <cctype>
#include <iostream>
#include <string>
#include "split.h"

using std::cin;
using std::cout;
using std::endl;
using std::isspace;
using std::string;

Vec<string> split(const string& s) {
  Vec<string> splitVector;
  typedef string::size_type string_size;
  string_size i = 0;

  while (i != s.size()) {
    while (i != s.size() && isspace(s[i]))
      ++i;

    string_size j = i;
    while (j != s.size() && !isspace(s[j]))
      ++j;

    if (i != j) {
      splitVector.push_back(s.substr(i, j - i));
      i = j;
    }
  }

  return splitVector;
}

... continued on the next post ...

[jetimms]

from Vec.h

#ifndef _GUARD_VEC_H_
  #define _GUARD_VEC_H_
  #include <algorithm>
  #include <memory>

  template <typename T> class Vec {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef size_t size_type;
    typedef T value_type;

    Vec() {create();}
    explicit Vec(size_type n, const T& val = T()) {create(n, val);}

    ~Vec() {uncreate();}
    Vec(const Vec& v) {create(v.begin(), v.end());}
    Vec& operator=(const Vec&);

    T& operator[](size_type i) {return data[i];}
    const T& operator[](size_type i) const {return data[i];}

    void push_back(const T& val) {
      if (avail == limit) {
        grow();
      }

      unchecked_append(val);
    }

    iterator erase(iterator position) {
      iterator next = position;

      if (position < avail) {
        ++next;
      }

      if (position >= data) {
        shrink(position);
        unchecked_remove(position);
      }

      return next;
    }

    void clear() {
      uncreate();
    }

    void insert(
      iterator position, 
      const_iterator first, 
      const_iterator last);
    
    size_type size() const {return avail - data;}

    iterator begin() {return data;}
    const_iterator begin() const {return data;}

    iterator end() {return avail;}
    const_iterator end() const {return avail;}

    bool empty() const {return data == avail;}
  private:
    iterator data;
    iterator avail;
    iterator limit;

    std::allocator<T> alloc;

    void create();
    void create(size_type n, const T& val);
    void create(const_iterator b, const_iterator e);
    void uncreate();
    void grow();
    void shrink(iterator position);
    void unchecked_append(const T& val);
    void unchecked_remove(iterator position);
  };

  template <typename T> Vec<T>& Vec<T>::operator=(const Vec<T>& rhs) {
    // check for self-assignment
    if (&rhs != this)
    {
      // free the array in the left-hand side
      uncreate();

      // copy elements from the right-hand to the left-hand side
      create(rhs.begin(), rhs.end());
    }
    return *this;
  }

  template <typename T> void Vec<T>::create() {
    data = avail = limit = NULL;
  }

  template <typename T> void Vec<T>::create(size_type n, const T& val) {
    data = alloc.allocate(n);
    avail = limit = data + n;
    std::uninitialized_fill(data, avail, val);
  }

  template <typename T>
  void Vec<T>::create(const_iterator b, const_iterator e) {
    data = alloc.allocate(e - b);
    avail = limit = std::uninitialized_copy(b, e, data);
  }

  template <typename T> void Vec<T>::uncreate() {
    if (data) {
      iterator it = avail;

      while ( it != data)
        alloc.destroy(--it);

      alloc.deallocate(data, limit - data);
    }

    data = avail = limit = 0;
  }

  template <typename T> void Vec<T>::grow() {
    size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = std::uninitialized_copy(data, avail, new_data);

    uncreate();

    data = new_data;
    avail = new_avail;
    limit = data + new_size;
  }

  template <typename T> void Vec<T>::unchecked_append(const T& val) {
    alloc.construct(avail++, val);
  }

  template <typename T> void Vec<T>::shrink(iterator position) {
    size_type new_size = std::max(limit - data - 1, ptrdiff_t(1));

    iterator new_data = alloc.allocate(new_size);
    iterator second_portion = std::uninitialized_copy(data, position - 1, new_data);
    iterator new_avail = std::uninitialized_copy(position + 1, avail, second_portion);

    avail = std::uninitialized_copy(new_data, new_avail, data);

    alloc.deallocate(new_data, new_size);

    --limit;
  }

  template <typename T> void Vec<T>::unchecked_remove(iterator position) {
    alloc.destroy(position);
  }

  template <typename T>
  void Vec<T>::insert(
    iterator position, 
    const_iterator first, 
    const_iterator last) {
    
    while (last - first > limit - avail){
      grow();
    }

    if (position == avail) {
      avail = std::uninitialized_copy(first, last, position);
    }
    else {
      iterator new_position = position + (last - first);
      avail = std::uninitialized_copy(position, avail, new_position);
      std::uninitialized_copy(first, last, position);
    }
  }
#endif 

That's it for the Vec class, no .cpp file.

BTW: Thanks for your help.

[jetimms]

I wonder if the <Bad Ptr> is a result of me compiling and running this on XP x64. I've checked the actual addresses of the bad pointers and they don't look bad, i.e. data <= avail <= limit.

The run-time error message doesn't actually come back until the insert statement is hit, in Vec.h.

When the insert method is called from vcat(), the first argument "joinedPictures.end()" should equal "joinedPictures::avail" inside the call to insert. It does not.

It is consistently lower than the data pointer's address. The thrown error is actually occuring inside uninitialized_copy.

Maybe I should just ignore the <Bad Ptr> I'm seeing in the debugger and focus on that.

[jetimms]

Hammurabi, I did implement the fix you suggested, "ignore the return value from uninitialized_copy inside of grow" and it did make a difference in the avail and limit.

Thanks for that suggestion.

There is still a runtime error occuring at uninitialized_copy inside of insert. I have determined that position is no longer relevant after grow() occurs. That is what is giving me the error.

Now, if I give an adjustment to position after each grow, I should fix that problem.

Whoo hoo! It works now!

Here's the changes I made:

from Vec.h

  template <typename T> void Vec<T>::grow() {
    size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

    iterator new_data = alloc.allocate(new_size);
//    iterator new_avail = std::uninitialized_copy(data, avail, new_data);
    std::uninitialized_copy(data, avail, new_data);  // dropping return
    iterator new_avail = new_data + (avail - data);  // new avail calc

    uncreate();

    data = new_data;
    avail = new_avail;
    limit = data + new_size;
  }
...
  template <typename T>
  void Vec<T>::insert(
    iterator position, 
    const_iterator first, 
    const_iterator last) {
    
    if (position >= data && position <= avail) {  // value check
      size_type positionIndex = position - data;  // location calculation

      while (last - first > limit - avail) {
        grow();
        position = data + positionIndex;  // repositioning position
      }

      if (position == avail) {
        avail = std::uninitialized_copy(first, last, position);
      }
      else {
        iterator new_position = position + (last - first);
//        avail = std::uninitialized_copy(position, avail, new_position);
        std::uninitialized_copy(position, avail, new_position);  // dropping return
        avail = new_position + (avail - position);  // new avail calc
        std::uninitialized_copy(first, last, position);
      }
    }

Thanks again, for the help and questions Ham and Pan!!!

[Hammurabi]

Nice job! Just remember that it's generally not a good idea to trace your bug into the implementation code too soon, since it's far more likely to be in your own code. :)

However, it looks like my suggestion was not important, at least for my implementation (WinXP with gcc compiler), since it works if you just assign uninitialized_copy's value to avail (or whatever). The real fix is the lines you added to insert:

    size_type positionIndex = position - data;

    while (last - first > limit - avail){
      grow();
      position = data + positionIndex;
    }

Again, nice job.