Re: libstdc++/8230: Buggy allocator behaviour

Re: libstdc++/8230: Buggy allocator behaviour

[bkoz]

Synopsis: Buggy allocator behaviour

State-Changed-From-To: feedback->closed
State-Changed-By: bkoz
State-Changed-When: Mon Nov 18 11:13:15 2002
State-Changed-Why:
    Fixed now.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=8230

Re: libstdc++/8230: Buggy allocator behaviour

[Richard Henderson]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Richard Henderson <rth@redhat.com>
To: Gabriel Dos Reis <gdr@integrable-solutions.net>
Cc: Matt Austern <austern@apple.com>, Benjamin Kosnik <bkoz@redhat.com>,
   bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org, jkanze@caicheuvreux.com,
   gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: Fri, 15 Nov 2002 14:41:38 -0800

 On Thu, Nov 14, 2002 at 11:27:17PM +0100, Gabriel Dos Reis wrote:
 > Maybe RTH could provide us with some datapoint here?
 
 "It depends".
 
 > | Second, if the answer to question 1 is "a lot": is there some sensible
 > | way to use this in the compiler itself?  I suppose it'd have to involve
 > | some ghastly macro hackery because of the bootstrap problem, but
 > | it we're talking big performance wins, it might be worth it.
 > 
 > If the answer to the first question is "a lot", then I agree with you
 > that it makes perfect sense to use it in the compiler itself.  I
 > could imagine something along the lines
 > 
 > #if !defined(__GNUC__) || __GNUC__ < 3  /* correct the version number */
 > #  define __builtin_expect(EXP, PROB) EXP
 > #endif
 > 
 > in system.h or wherever appropriate.
 
 I don't think it's worth it, except _possibly_ in the 
 ENABLE_CHECKING macros.
 
 
 r~

Re: libstdc++/8230: Buggy allocator behaviour

[Gabriel Dos Reis]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Gabriel Dos Reis <gdr@integrable-solutions.net>
To: Matt Austern <austern@apple.com>
Cc: Benjamin Kosnik <bkoz@redhat.com>, bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org,
   jkanze@caicheuvreux.com, gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org,
   rth@redhat.com
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: 14 Nov 2002 23:27:17 +0100

 Matt Austern <austern@apple.com> writes:
 
 [...]
 
 | > In general, I would like to see us starting using use 
 | > __builtin_expect()
 | > at places where we do checks for limits cases.  Thoughts?
 | 
 | Two questions.
 | 
 | First, is it known how much of a speedup this gives on typical 
 | platforms?
 
 I didn't make measurements by myself but I'm trusting its implementor
 (RTH) :-)
 
 Maybe RTH could provide us with some datapoint here?
 
 | Second, if the answer to question 1 is "a lot": is there some sensible
 | way to use this in the compiler itself?  I suppose it'd have to involve
 | some ghastly macro hackery because of the bootstrap problem, but
 | it we're talking big performance wins, it might be worth it.
 
 If the answer to the first question is "a lot", then I agree with you
 that it makes perfect sense to use it in the compiler itself.  I
 could imagine something along the lines
 
 #if !defined(__GNUC__) || __GNUC__ < 3  /* correct the version number */
 #  define __builtin_expect(EXP, PROB) EXP
 #endif
 
 in system.h or wherever appropriate.
 
 -- Gaby

Re: libstdc++/8230: Buggy allocator behaviour

[Matt Austern]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Matt Austern <austern@apple.com>
To: Gabriel Dos Reis <gdr@integrable-solutions.net>
Cc: Benjamin Kosnik <bkoz@redhat.com>, bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org,
   jkanze@caicheuvreux.com, gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: Thu, 14 Nov 2002 14:10:55 -0800

 On Thursday, November 14, 2002, at 12:39 PM, Gabriel Dos Reis wrote:
 
 > Benjamin Kosnik <bkoz@redhat.com> writes:
 >
 > | See attached patch for a way to fix this with the pool allocators.
 >
 > I agree with your patch.
 >
 > The following comment is for possible improvements.  What about using
 >
 >    if (__builtin_expect(__ret == 0, 0))
 >        __throw_bad_alloc("allocate::allocate");
 >
 > ?
 > That gives a hint to the compiler that the branch is expected to be
 > taken very unfrequently, and it should make scheduling accordingly.
 >
 > In general, I would like to see us starting using use 
 > __builtin_expect()
 > at places where we do checks for limits cases.  Thoughts?
 
 Two questions.
 
 First, is it known how much of a speedup this gives on typical 
 platforms?
 
 Second, if the answer to question 1 is "a lot": is there some sensible
 way to use this in the compiler itself?  I suppose it'd have to involve
 some ghastly macro hackery because of the bootstrap problem, but
 it we're talking big performance wins, it might be worth it.
 
 			--Matt
 

Re: libstdc++/8230: Buggy allocator behaviour

[Gabriel Dos Reis]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Gabriel Dos Reis <gdr@integrable-solutions.net>
To: Benjamin Kosnik <bkoz@redhat.com>
Cc: bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org, jkanze@caicheuvreux.com,
   gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: 14 Nov 2002 21:39:50 +0100

 Benjamin Kosnik <bkoz@redhat.com> writes:
 
 | See attached patch for a way to fix this with the pool allocators.
 
 I agree with your patch.
 
 The following comment is for possible improvements.  What about using
 
    if (__builtin_expect(__ret == 0, 0))
        __throw_bad_alloc("allocate::allocate");
 
 ?
 That gives a hint to the compiler that the branch is expected to be
 taken very unfrequently, and it should make scheduling accordingly.
 
 In general, I would like to see us starting using use __builtin_expect()
 at places where we do checks for limits cases.  Thoughts? 
 
 -- Gaby

Re: libstdc++/8230: Buggy allocator behaviour

[Gabriel Dos Reis]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Gabriel Dos Reis <gdr@integrable-solutions.net>
To: Benjamin Kosnik <bkoz@redhat.com>
Cc: bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org, jkanze@caicheuvreux.com,
   gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: 14 Nov 2002 21:33:20 +0100

 Benjamin Kosnik <bkoz@redhat.com> writes:
 
 [...]
 
 | >This coredumps on my machine using current source.  The problem here is
 | >that std::allocator<> is not checking the bounds as required and it is
 | >lying.
 | 
 | Correct, with the pool allocators. If you add GLIBCPP_FORCE_NEW
 | everything is ok.
 
 Thanks!
 
 | See attached patch for a way to fix this with the pool allocators.
 | >
 | >I'm also nervous about:
 | >
 | >   std::vector<int> v;
 | >   v.resize(v.max_size());
 | >
 | >   v[v.max_size() - 1] = 2002;
 | >
 | >I didn't test it with your patch.
 | 
 | My patch is only for reserve, as it's expected to throw length_error.
 | I believe it's still correct, regardless of resolving this issue.
 
 Yes, you're right.
 
 | For resize, the above issue comes into play.
 | 
 | On a completely unrelated note, what's up with std::vector and all the gooey 
 | allocator typedefs? Ick.
 
 [ I'm not sure I understand correctly which part you're referring to.
   I'll try answer what I understood from your question.  Please don't
   hesitate to correct me if I'm on the wrong track.  ]
 
 Well, the allocator_type typedef game is what we've got to write to
 simulate "typedef template".  Basically one wants to be able to get an
 allocator for the familly of allocator supplied to std::vector<>.
 
 | The allocator_type typedef is always allocator, as far as I can tell.
 | And _Alloc_type (should be __underlying_allocator or whatever) seems
 | superfluous. Instead of typedefing the base type all the time, with g++
 | one can just use the name of the template proper.
 
 Probably not the name of the template but the name of the
 template-parameter _Alloc.  But, I suspect that for not duplicating
 the way the allocator is referred to, it is just safe to use
 _Base::allocator_type -- note that we have to typedef that name to
 allocator_type in std::vector<> anyway.
 
 Maybe Matt has better explanations.
 
 -- Gaby

Re: libstdc++/8230: Buggy allocator behaviour

[Benjamin Kosnik]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Benjamin Kosnik <bkoz@redhat.com>
To: Benjamin Kosnik <bkoz@redhat.com>
Cc: gdr@integrable-solutions.net, bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org,
   jkanze@caicheuvreux.com, gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: Thu, 14 Nov 2002 13:50:13 -0600

 >The allocator_type typedef is always allocator, as far as I can tell.
 
 Ok, coffee break. This is wrong, by inspection. 
 
 >And _Alloc_type (should be __underlying_allocator or whatever) seems
 >superfluous. 
 
 The points about a simpler way still seem true though.
 
 -benjamin

Re: libstdc++/8230: Buggy allocator behaviour

[Benjamin Kosnik]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Benjamin Kosnik <bkoz@redhat.com>
To: Gabriel Dos Reis <gdr@integrable-solutions.net>
Cc: bkoz@gcc.gnu.org, gcc-bugs@gcc.gnu.org, jkanze@caicheuvreux.com,
   gcc-gnats@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: Thu, 14 Nov 2002 13:44:01 -0600

 This is a multi-part message in MIME format.
 
 --Multipart_Thu__14_Nov_2002_13:44:01_-0600_0841f4a0
 Content-Type: text/plain; charset=US-ASCII
 Content-Transfer-Encoding: 7bit
 
 
 >20.4.1.1 allocator members
 >
 >2/
 >  pointer allocator(size_type n, allocator<void>::const_pointer = 0);
 >
 >7/
 >  Throws: bad_alloc if the storage cannot be obtained
 
 Got it, thanks for the clarification.
 
 >int main()
 >{
 >   try {
 >      std::allocator<int> alloc;
 >      const std::allocator<int>::size_type n = alloc.max_size();
 >      int* p = alloc.allocate(n + 1);
 >      p[n] = 2002;
 >      std::cout << p[n] << std::endl;
 >   } catch(const std::bad_alloc& e) {
 >      std::cerr << e.what() << std::endl;
 >   }
 >}
 >This coredumps on my machine using current source.  The problem here is
 >that std::allocator<> is not checking the bounds as required and it is
 >lying.
 
 Correct, with the pool allocators. If you add GLIBCPP_FORCE_NEW
 everything is ok.
 
 See attached patch for a way to fix this with the pool allocators.
 >
 >I'm also nervous about:
 >
 >   std::vector<int> v;
 >   v.resize(v.max_size());
 >
 >   v[v.max_size() - 1] = 2002;
 >
 >I didn't test it with your patch.
 
 My patch is only for reserve, as it's expected to throw length_error.
 I believe it's still correct, regardless of resolving this issue.
 For resize, the above issue comes into play.
 
 On a completely unrelated note, what's up with std::vector and all the gooey 
 allocator typedefs? Ick.
 
 The allocator_type typedef is always allocator, as far as I can tell.
 And _Alloc_type (should be __underlying_allocator or whatever) seems
 superfluous. Instead of typedefing the base type all the time, with g++
 one can just use the name of the template proper. There's got to be a
 cleaner way to do a lot of this. Matt?
 
 best,
 benjamin
 --Multipart_Thu__14_Nov_2002_13:44:01_-0600_0841f4a0
 Content-Type: application/octet-stream;
  name="p.20021114-1"
 Content-Disposition: attachment;
  filename="p.20021114-1"
 Content-Transfer-Encoding: base64
 
 SW5kZXg6IHN0bF9hbGxvYy5oCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09
 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KUkNTIGZpbGU6IC9jdnMvZ2NjL2djYy9saWJz
 dGRjKystdjMvaW5jbHVkZS9iaXRzL3N0bF9hbGxvYy5oLHYKcmV0cmlldmluZyByZXZpc2lvbiAx
 LjI1CmRpZmYgLWMgLXAgLXIxLjI1IHN0bF9hbGxvYy5oCioqKiBzdGxfYWxsb2MuaAkxOCBPY3Qg
 MjAwMiAyMDo1Mjo1NSAtMDAwMAkxLjI1Ci0tLSBzdGxfYWxsb2MuaAkxNCBOb3YgMjAwMiAxOToz
 NTo0NyAtMDAwMAoqKioqKioqKioqKioqKiogbmFtZXNwYWNlIHN0ZAoqKiogNjY5LDY4MSAqKioq
 CiAgICAgICAgY29uc3RfcG9pbnRlcgogICAgICAgIGFkZHJlc3MoY29uc3RfcmVmZXJlbmNlIF9f
 eCkgY29uc3QgeyByZXR1cm4gJl9feDsgfQogIAohICAgICAgIC8vIF9fbiBpcyBwZXJtaXR0ZWQg
 dG8gYmUgMC4gIFRoZSBDKysgc3RhbmRhcmQgc2F5cyBub3RoaW5nIGFib3V0IHdoYXQKISAgICAg
 ICAvLyB0aGUgcmV0dXJuIHZhbHVlIGlzIHdoZW4gX19uID09IDAuCiAgICAgICAgX1RwKgogICAg
 ICAgIGFsbG9jYXRlKHNpemVfdHlwZSBfX24sIGNvbnN0IHZvaWQqID0gMCkKICAgICAgICB7CiEg
 ICAgICAgICByZXR1cm4gX19uICE9IDAKISAgICAgICAgICAgPyBzdGF0aWNfY2FzdDxfVHAqPihf
 QWxsb2M6OmFsbG9jYXRlKF9fbiAqIHNpemVvZihfVHApKSkgOiAwOwogICAgICAgIH0KICAKICAg
 ICAgICAvLyBfX3AgaXMgbm90IHBlcm1pdHRlZCB0byBiZSBhIG51bGwgcG9pbnRlci4KLS0tIDY2
 OSw2OTMgLS0tLQogICAgICAgIGNvbnN0X3BvaW50ZXIKICAgICAgICBhZGRyZXNzKGNvbnN0X3Jl
 ZmVyZW5jZSBfX3gpIGNvbnN0IHsgcmV0dXJuICZfX3g7IH0KICAKISAgICAgICAvLyBOQjogX19u
 IGlzIHBlcm1pdHRlZCB0byBiZSAwLiAgVGhlIEMrKyBzdGFuZGFyZCBzYXlzIG5vdGhpbmcKISAg
 ICAgICAvLyBhYm91dCB3aGF0IHRoZSByZXR1cm4gdmFsdWUgaXMgd2hlbiBfX24gPT0gMC4KICAg
 ICAgICBfVHAqCiAgICAgICAgYWxsb2NhdGUoc2l6ZV90eXBlIF9fbiwgY29uc3Qgdm9pZCogPSAw
 KQogICAgICAgIHsKISAJX1RwKiBfX3JldCA9IDA7CiEgCWlmIChfX24pCiEgCSAgewohIAkgICAg
 Ly8gVGhlIHN0YW5kYXJkIG1hbmRhdGVzIHRoZSB1c2Ugb2YgOjpvcGVyYXRvciBuZXcsIGFuZAoh
 IAkgICAgLy8gdGhyb3dpbmcgYmFkX2FsbG9jIGlmIGFsbG9jYXRpb24gZmFpbHMuIEhvd2V2ZXIs
 IHRoaXMKISAJICAgIC8vIGltcGxlbWVudGF0aW9uIGFsbG93cyBvdGhlciBtZW1vcnkgYWxsb2Nh
 dGlvbiBzY2hlbWVzCiEgCSAgICAvLyBiZXNpZGVzIG9wZXJhdG9yIG5ldywgYW5kIHNvbWUgb2Yg
 dGhlbSBkb24ndCB0aHJvdwohIAkgICAgLy8gYmFkX2FsbG9jIGJ5IGRlZmF1bHQgaWYgdGhleSBm
 YWlsLiBUaHVzLCBhZGQgdGhlIGNoZWNrCiEgCSAgICAvLyBiZWxvdy4KISAJICAgIF9fcmV0ID0g
 c3RhdGljX2Nhc3Q8X1RwKj4oX0FsbG9jOjphbGxvY2F0ZShfX24gKiBzaXplb2YoX1RwKSkpOwoh
 IAkgICAgaWYgKCFfX3JldCkKISAJICAgICAgX190aHJvd19iYWRfYWxsb2MoImFsbG9jYXRvcjo6
 YWxsb2NhdGUiKTsKISAJICB9CiEgCXJldHVybiBfX3JldDsKICAgICAgICB9CiAgCiAgICAgICAg
 Ly8gX19wIGlzIG5vdCBwZXJtaXR0ZWQgdG8gYmUgYSBudWxsIHBvaW50ZXIuCg==
 
 --Multipart_Thu__14_Nov_2002_13:44:01_-0600_0841f4a0--

Re: libstdc++/8230: Buggy allocator behaviour

[Gabriel Dos Reis]

The following reply was made to PR libstdc++/8230; it has been noted by GNATS.

From: Gabriel Dos Reis <gdr@integrable-solutions.net>
To: bkoz@gcc.gnu.org
Cc: gcc-bugs@gcc.gnu.org, jkanze@caicheuvreux.com, gcc-gnats@gcc.gnu.org,
   libstdc++@gcc.gnu.org
Subject: Re: libstdc++/8230: Buggy allocator behaviour
Date: 14 Nov 2002 15:59:43 +0100

 bkoz@gcc.gnu.org writes:
 
 | Synopsis: Buggy allocator behaviour
 | 
 | Responsible-Changed-From-To: unassigned->bkoz
 | Responsible-Changed-By: bkoz
 | Responsible-Changed-When: Wed Nov 13 14:19:11 2002
 | Responsible-Changed-Why:
 |     Mine.
 | State-Changed-From-To: open->feedback
 | State-Changed-By: bkoz
 | State-Changed-When: Wed Nov 13 14:19:11 2002
 | State-Changed-Why:
 |     I don't think this is an allocator::allocate issue per se. The member function reserve is only in std::vector and std::vector<bool>, and the standard says
 
 Hi Benjamin,
 
   This issue is a conjugation of both std::allocator<> and
 std::vector<> ill-behaviour.  Fixing std::vector<> fixes a part of
 the problem (i.e. the testcase provided will pass), but leaves
 completely unfixed the std::allocator<> bits as required by the
 standard: 
 
 20.4.1.1 allocator members
 
 2/
   pointer allocator(size_type n, allocator<void>::const_pointer = 0);
 
 7/
   Throws: bad_alloc if the storage cannot be obtained
 
 20.4.1.1/11
   size_type max_size() const throw();
   returns the largest value N for which the call allocate(N, 0) might
   succeed. 
 
 Now consider
 
 int main()
 {
    try {
       std::allocator<int> alloc;
       const std::allocator<int>::size_type n = alloc.max_size();
       int* p = alloc.allocate(n + 1);
       p[n] = 2002;
       std::cout << p[n] << std::endl;
    } catch(const std::bad_alloc& e) {
       std::cerr << e.what() << std::endl;
    }
 }
 
 This coredumps on my machine using current source.  The problem here is
 that std::allocator<> is not checking the bounds as required and it is
 lying.
 
 On fr.comp.lang.c++, I developed a theory to the effect that
 std::vector<> may always not check the bounds and still remain
 conformant *provided* that the allocator is doing the right thing.  
 
 |     23.2.4.2 - vector capacity
 |     
 |     -4- Throws: length_error if n > max_size().* 
 |     
 |     Where allocator::allocate doesn't know what vector::max_size is. 
 
 Agreed.
 
 |     
 |     This fix brings the code up to conformance, and is the best fix I think.
 
 It, however, does not address the std::allocator<> ill-behaviour.
 
 I'm also nervous about:
 
    std::vector<int> v;
    v.resize(v.max_size());
 
    v[v.max_size() - 1] = 2002;
 
 I didn't test it with your patch.
 
 -- Gaby

Re: libstdc++/8230: Buggy allocator behaviour

[bkoz]

Synopsis: Buggy allocator behaviour

Responsible-Changed-From-To: unassigned->bkoz
Responsible-Changed-By: bkoz
Responsible-Changed-When: Wed Nov 13 14:19:11 2002
Responsible-Changed-Why:
    Mine.
State-Changed-From-To: open->feedback
State-Changed-By: bkoz
State-Changed-When: Wed Nov 13 14:19:11 2002
State-Changed-Why:
    I don't think this is an allocator::allocate issue per se. The member function reserve is only in std::vector and std::vector<bool>, and the standard says
    
    23.2.4.2 - vector capacity
    
    -4- Throws: length_error if n > max_size().* 
    
    Where allocator::allocate doesn't know what vector::max_size is. 
    
    This fix brings the code up to conformance, and is the best fix I think.
    
    -benjamin

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=8230

libstdc++/8230: Buggy allocator behaviour

[gdr]

>Number:         8230
>Category:       libstdc++
>Synopsis:       Buggy allocator behaviour
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Oct 15 05:56:01 PDT 2002
>Closed-Date:
>Last-Modified:
>Originator:     James Kanze
>Release:        all GCC releases.
>Organization:
>Environment:
Plateform independent, though the program below
displays the buggy behaviour on IA32.
>Description:
std:allocator<T>::allocate(n) does not check for possible 
overflow before "folding" sizeof(T) * n.
>How-To-Repeat:

>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: text/plain; name="jk.C"
Content-Disposition: inline; filename="jk.C"

#include <vector>
#include <iostream>

int main()
{
   static size_t const size = 1024 * 1024 * 1024 ;
   std::vector< int >  array ;
   try {
      array.reserve( size ) ;
   } catch ( std::exception const& error ) {
      std::cerr << "Error: " << error.what() << " (type = " <<
         typeid( error ).name() << ")\n" ;
      return 2 ;
   }
   return 0 ;
}