[Bug libstdc++/43483] New: STL sort SIGSEV

[Bug libstdc++/43483] New: STL sort SIGSEV

[richardlee at snowshoefox dot com]

The STL sort implementation in stl_algo.h SIGSEVs under certain conditions due
to not checking the position of the __first and __last iterator positions.

Here is a diff between a working version and the buggy version in 4.4.1:

2228d2227
<       int len = __last - __first;
2231c2230
<         while (__first != __last && __comp(*__first, __pivot))
---
> 	  while (__comp(*__first, __pivot))
2233,2234c2232,2233
<         --__last; 
<         while (len-- > 0 && __comp(__pivot, *__last))
---
> 	  --__last;
> 	  while (__comp(__pivot, *__last))

The fix is to make sure __first and __last stays within the boundary of
[__first, __last).


-- 
           Summary: STL sort SIGSEV
           Product: gcc
           Version: 4.4.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: richardlee at snowshoefox dot com
  GCC host triplet: 2.6.31-20-generic #58-Ubuntu SMP x86_64 GNU/Linux


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

[Bug libstdc++/43483] STL sort SIGSEV

[paolo dot carlini at oracle dot com]

------- Comment #1 from paolo dot carlini at oracle dot com  2010-03-22 20:05 -------
Please provide a complete, self-contained testcase, otherwise nothing will
happen.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


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

[Bug libstdc++/43483] STL sort SIGSEV

[richardlee at snowshoefox dot com]

------- Comment #2 from richardlee at snowshoefox dot com  2010-03-22 20:18 -------
Created an attachment (id=20165)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20165&action=view)
Proposed patch using 'patch -up'... run patch in the 4.4.1/bits/ folder.


-- 


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

[Bug libstdc++/43483] STL sort SIGSEV

[paolo dot carlini at oracle dot com]

------- Comment #3 from paolo dot carlini at oracle dot com  2010-03-22 20:26 -------
The patch is incorrect for various formal reasons (eg, should be against
current mainline not vs a random old release; should use difference_type, not
int; should use an uglified __len) + should come with a detailed analysis and a
ChangeLog entry. Even more important now, at this preliminary stage, it lacks a
small, self contained testcase, useful to reproduce the proble: missing it the
PR will be soon closed.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |normal


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

[Bug libstdc++/43483] STL sort SIGSEV

[richardlee at snowshoefox dot com]

------- Comment #4 from richardlee at snowshoefox dot com  2010-03-22 20:55 -------
Here is a very simplified version of the scenario that triggered the bug.

bool compare(int t1, int t2) {
        return true;
}

int main(int argc, char** argv) {
        vector<int> v;
        v.assign(32, 2);
        cout << v.size() << endl; 
        sort(v.begin(), v.end(), compare);
}


-- 


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

[Bug libstdc++/43483] STL sort SIGSEV

[paolo dot carlini at oracle dot com]

------- Comment #5 from paolo dot carlini at oracle dot com  2010-03-22 21:24 -------
compare is not irreflexive, as it must be per 25.3/4.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |INVALID


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