egcs-1.0 memory bug in <string>

[Ian Haggard]

R. Ebert wrote:
> 
> Depending on the size of your virtual memory the following program
> crashes after 30 to 500 loops.
> 
> int main ()
> {
>   // string -  BUG 3 - Demo
>   string s1 = "a";
>   string s2;
> 
>   for (int i=0; i<70; i++)
>   {
>     s2 = s1;        // now two references to rep
>     s1[1] = 'a';    // s1 gets duplicated via unique()
>     cout << s1.capacity() << endl;  // ... and grows and grows
>   }
> }
> 
> Virtual memory exceeded in `new'
> 
> The problem is in
> 
>   void unique () { if (rep ()->ref > 1) alloc (capacity (), true); }
>                                                ^^^^^^^^

Actually, the problem is not just here, but rather it is also caused by the
interactions between these two functions:

inline basic_string <charT, traits>::Rep * basic_string <charT, traits>::Rep::
create (size_t extra)
{
  extra = frob_size (extra + 1);
  //etc.
}

void basic_string <charT, traits>::
alloc (size_t size, bool save)
{
  if (! check_realloc (size))
    return;

  Rep *p = Rep::create (size);
  // etc.
}

Because create is being called from alloc with extra=capacity() (and capacity
is already a frob_size'd number), adding 1 to extra causes it to be bumped up
to the next frob_size().  Which is the next power of two, of course.

> Thus a more correct implementation might be
> 
>   void unique () { if (rep ()->ref > 1) alloc (length (), true); }

I agree here that passing length() is the best solution.

> 
> or 
> 
>   void unique () { if (rep ()->ref > 1) alloc (capacity () - 1, true); }

I agree that this would work (provided the user is using the default
frob_size() function), but the reason it would work is because it undoes the
extra+1 in the create function.  A bit subtle and difficult to maintain for my
tastes :^)  Also, if the user is not using the default frob_size() function,
and their function is just something like frob_size (size_t s) { return s*5/4;
} or some other space-saving frob_size, then the bug would reappear -- the
"principle" that's being violated here is that no number should be frob_size'd
more than once.
-- 
Ian Haggard  ||  ian@shellus.com (work)  ||  IanHaggard@juno.com (home)
GNU/Linux -- "Oh, no, Mr Bill!" || #define employer_opinion !my_opinion