[Bug libstdc++/31370] New: resizing bugs in std::vector

[Bug libstdc++/31370] New: resizing bugs in std::vector

[gcc at severeweblint dot org]

Pre-4.0, vector had a bunch of nasty error cases when resizing overflowed a
size_t. Change 89377 fixed some of them. But

1) vector<bool>'s copy (yuck) of the relevant functions weren't updated

2) vector<bool>'s max_size is incorrect. currently it is set to the maximum
size_t. but because vector<bool>'s iterators aren't directly pointers, and the
iterator arithmetic takes ssize_t as arguments, it can't tolerate sizes that
don't fit in an ssize_t. because of the round up to the nearest word, the
correct max_size is SIZE_MAX rounded down to the nearest word.

3) if doubling a vector size exceeds max_size, the code will go ahead and ask
the allocator for it. It seems nicer to clamp the size to max_size, although a
bad_alloc is to be expected either way. I'd mostly argue that the vector code
should clamp at max_size to avoid relying on the allocator to range check
properly.


-- 
           Summary: resizing bugs in std::vector
           Product: gcc
           Version: 4.1.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: gcc at severeweblint dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector

[gcc at severeweblint dot org]

------- Comment #1 from gcc at severeweblint dot org  2007-03-27 04:08 -------
Created an attachment (id=13292)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13292&action=view)
testcase

This little program pushes some of the boundary cases. It ought to print
nothing and exit cleanly. Currently it complains and crashes.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector

[gcc at severeweblint dot org]

------- Comment #2 from gcc at severeweblint dot org  2007-03-27 04:20 -------
Created an attachment (id=13293)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13293&action=view)
patch

This patch fixes all the problems in the cheapest possible way. With it the
attached testcase succeedds. It does not incorporate the testcase attachment
into the gcc testsuite, although that surely ought to be done. (I got confused
by the makefile for the testsuite. sorry)

Note there are other approaches to fixing these bugs that might be better in
the long term:

1) It is plainly bad that vector<bool> has a copy of code from vector. It is
likewise poor that each has 3 places that deal in resizing, each of which needs
similar defensive logic. 

2) vector<bool>::iterator ought to use a 64-bit int for sizes, even in a 32-bit
environment, since it could have sizes larger than the pointer limitation. But
I'm not positive that that is doable. It may not be possible to match function
signatures to vector as needed. The limited size may be best considered a cost
of the mistake of making a bit vector a specialization of vector, instead of
its own class.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-03-27 07:04 -------
vector<bool> should really go away.  It is not really a container at all.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|resizing bugs in std::vector|resizing bugs in
                   |                            |std::vector<bool>


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[fang at csl dot cornell dot edu]

------- Comment #4 from fang at csl dot cornell dot edu  2007-03-27 08:52 -------
Poor vector<bool>, being disrespected as a second-class container once again...
:P


-- 

fang at csl dot cornell dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fang at csl dot cornell dot
                   |                            |edu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[pcarlini at suse dot de]

------- Comment #5 from pcarlini at suse dot de  2007-03-27 09:07 -------
Thanks. On the mainline and 4_2-branch we have new definitions of max_size,
taking into account, as should be, allocator::max_size. Can you please check
the vector<bool> bits in this light? (well, about the status of vector<bool>,
Andrew is overstating the issue a bit, but mostly right: we aren't that much
motivated in improving it, but we have to do that anyway as long as it stays in
the standard, recently we improved its performance quite a bit in a few areas).

One final observation: if you feel like contributing other improvements, please
consider filing the necessary Copyright Assignment paperworks: your patch will
be close to the maximum we can get in as a "small contribution" under relaxed
rules:

  http://gcc.gnu.org/contribute.html


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pcarlini at suse dot de
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-03-27 09:07:36
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[gcc at severeweblint dot org]

------- Comment #6 from gcc at severeweblint dot org  2007-03-27 20:27 -------
4.2 doesn't fix any of the problems, but it does make the max_size
issue a bit more confusing.

There is a subtle relationship between vector size and
pointers. Pointers can address only SIZE_MAX memory. But iterators
takes ssize_t as arguments to addition and subtraction operators, so
vector size should be limited to SSIZE_MAX. For sizeof(_Tp) of at
least 2 bytes, there is no problem. The pointer limitation implies a
size limit of SIZE_MAX / sizeof(_Tp) which is less than SSIZE_MAX. For
sizeof(_Tp) of one byte, things deserve to be broken, but manage
not to be. The fact that for two size_t x1 and x2, it is always true
that size_t(x1+x2) == size_t(x1+ssize_t(y)) manages to rescue the
situation.

But for vector<bool>, things break down completely and the max_size
becomes limited by SSIZE_MAX, not the pointer limitation. Worse,
because of the round up to the nearest word, the max_size actually has
to be SSIZE_MAX rounded DOWN to the nearest word. 

So allowing for the allocator to have its own size limit, the
implementation of max_size has to become

size_type
max_size() const
{   
  const size_type __isize = SSIZE_MAX - int(_S_word_bit) + 1;
  const size_type __asize = _M_get_Bit_allocator().max_size(); 
  return (__asize < __isize / size_type(_S_word_bit) ?
          __asize * size_type(_S_word_bit) : __isize);
}

Note that it probably isn't correct to assume that difference_type is
a ssize_t, and therefore has maximum SSIZE_MAX, but I don't see what
the correct way to ask what the maximum value representable by
difference_type is.

I'm fine with filling out copyright assignment paperwork, but I didn't see the
form at the link you gave me.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[pcarlini at suse dot de]

------- Comment #7 from pcarlini at suse dot de  2007-03-27 21:03 -------
Two quick replies:

> 4.2 doesn't fix any of the problems, but it does make the max_size
> issue a bit more confusing.

Thanks, this is encouraging ;) In any case, nobody said 4.2 fixed any of those
problems. However, for sure, any proposed patch / fix targets first mainline,
not the release branches.

> Note that it probably isn't correct to assume that difference_type is
> a ssize_t, and therefore has maximum SSIZE_MAX, but I don't see what
> the correct way to ask what the maximum value representable by
> difference_type is.

Why not numeric_limits<difference_type>::max() ?

> I'm fine with filling out copyright assignment paperwork, but I didn't see the
> form at the link you gave me.

Again, nobody said the form was there. I pointed you at that general
information page because I was under the - probably not too far from the truth
- impression that you was not familiar with our general directions for
contributors. If you need the forms, please send a message to assignments@.

In any case, that kind of paperwork is not needed for the present work, but, if
possible, please let's figure out a way to deal with the issues in a "C++"
(C++03, actually) way, which means using numeric_limits, not assuming specific
types for difference_type, size_type and so on, not using types likes ssize_t
which do not exist in the current C++ standard (*). Finally, I repeat myself,
any patch shall target mainline first.

I look forward to see your improved proposal.

(*) ssize_t is mentioned only once, in note 266. If we really need a type
equivalent for all practical matters to such Posix type, we have to find a way
to construct one on the fly, for example by implementing an __add_signed
(similar to the currently available __add_unsigned, in ext/type_traits.h) 


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[pcarlini at suse dot de]

------- Comment #8 from pcarlini at suse dot de  2007-03-31 17:52 -------
Taking care of it.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|NEW                         |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[paolo at gcc dot gnu dot org]

------- Comment #9 from paolo at gcc dot gnu dot org  2007-04-02 11:16 -------
Subject: Bug 31370

Author: paolo
Date: Mon Apr  2 11:15:50 2007
New Revision: 123424

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=123424
Log:
2007-04-02  Matthew Levine  <gcc@severeweblint.org>
            Paolo Carlini  <pcarlini@suse.de>

        PR libstdc++/31370
        * include/bits/stl_bvector.h (vector<bool>::max_size): Fix.
        (vector<bool>::_M_check_len): Add.
        * include/bits/vector.tcc (_M_fill_insert(iterator, size_type, bool),
        _M_insert_range(iterator, _ForwardIterator, _ForwardIterator,
        std::forward_iterator_tag), _M_insert_aux(iterator, bool)): Use it.
        * testsuite/23_containers/vector/bool/modifiers/insert/31370.cc: New.
        * testsuite/23_containers/vector/bool/capacity/29134.cc: Adjust.

        * include/bits/stl_vector.h (vector<>::_M_check_len): Add.
        * include/bits/vector.tcc (_M_insert_aux(iterator, const _Tp&),
        _M_fill_insert(iterator, size_type, const value_type&),
        _M_range_insert(iterator, _ForwardIterator, _ForwardIterator,
        std::forward_iterator_tag)): Use it.

Added:
   
trunk/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_bvector.h
    trunk/libstdc++-v3/include/bits/stl_vector.h
    trunk/libstdc++-v3/include/bits/vector.tcc
    trunk/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370

[Bug libstdc++/31370] resizing bugs in std::vector<bool>

[pcarlini at suse dot de]

------- Comment #10 from pcarlini at suse dot de  2007-04-02 11:19 -------
Fixed for 4.3.0.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31370