diff mbox

[libstdc++-v3,parallel,mode] Avoid taking address of dereferenced random access iterator

Message ID 4D789E41.6020903@kit.edu
State New
Headers show

Commit Message

Johannes Singler March 10, 2011, 9:47 a.m. UTC 
The attached patch patch solves a conformance problem of the parallel 
mode helper routine multiseq_partition.  I have added a test case for 
that.  multiseq_selection has similar problems, but is unused, so I plan 
to remove that completely (which might ask for renaming of the file and 
the test).

Should I use unique_ptr (or alloca, or something similar) here for a 
better exception safety (this routine is not parallel itself)?
Is it the appropriate place for the "unit test"?  It is used in the 
parallel sort.

Tested x86_64-unknown-linux-gnu: No regressions


2011-03-10  Johannes Singler  <singler@kit.edu>

         * include/parallel/multiseq_selection.h (multiseq_partition):
         Copy-construct _ValueType element on demand on heap, do not
         take address of dereferenced random access iterator.
         Remove unused code that has the same problem.
         * testsuite/25_algorithms/sort/multiseq_selection.cc:
         New unit test for multiseq_partition.

Johannes

Comments

Jonathan Wakely March 10, 2011, 10:37 a.m. UTC | #1 
On 10 March 2011 09:47, Johannes Singler wrote:
> The attached patch patch solves a conformance problem of the parallel mode
> helper routine multiseq_partition.  I have added a test case for that.
>  multiseq_selection has similar problems, but is unused, so I plan to remove
> that completely (which might ask for renaming of the file and the test).

Please update the copyright date in the changed file as well.

> Should I use unique_ptr (or alloca, or something similar) here for a better
> exception safety (this routine is not parallel itself)?

unique_ptr is C++0x only, auto_ptr would work.  But I see other heap
allocation in that function are already unguarded so there doesn't
seem to be much point guarding one and not the others.  How about
defining a local RAII type (and combining the three allocations into
one) e.g.

      struct _Guard
      {
          _DifferenceType* _M_ns;

          ~_Guard() { delete[] _M_ns; }
      } __guard = { };

      __guard._M_ns = new _DifferenceType[__m*3];

      _DifferenceType* __ns = __guard._M_ns;
      _DifferenceType* __a = __guard._M_ns + __m;
      _DifferenceType* __b = __guard._M_ns + 2*__m;
      _DifferenceType __l;

That ensures the _Guard destructor will clean up on exiting the
function, so you can remove the delete statements.

and
std::auto_ptr<_ValueType> __lmax;
...
  __lmax.reset(new _ValueType(__S(__i)[__a[__i] - 1]));
etc.
Johannes Singler March 10, 2011, 3:02 p.m. UTC | #2 
On 03/10/2011 11:37 AM, Jonathan Wakely wrote:
> On 10 March 2011 09:47, Johannes Singler wrote:
>> The attached patch patch solves a conformance problem of the parallel mode
>> helper routine multiseq_partition.  I have added a test case for that.
>>   multiseq_selection has similar problems, but is unused, so I plan to remove
>> that completely (which might ask for renaming of the file and the test).
>
> Please update the copyright date in the changed file as well.

Done.

>> Should I use unique_ptr (or alloca, or something similar) here for a better
>> exception safety (this routine is not parallel itself)?
>
> unique_ptr is C++0x only, auto_ptr would work.  But I see other heap
> allocation in that function are already unguarded so there doesn't
> seem to be much point guarding one and not the others.  How about
> defining a local RAII type (and combining the three allocations into
> one) e.g.
>
>        struct _Guard
>        {
>            _DifferenceType* _M_ns;
>
>            ~_Guard() { delete[] _M_ns; }
>        } __guard = { };
>
>        __guard._M_ns = new _DifferenceType[__m*3];
>
>        _DifferenceType* __ns = __guard._M_ns;
>        _DifferenceType* __a = __guard._M_ns + __m;
>        _DifferenceType* __b = __guard._M_ns + 2*__m;
>        _DifferenceType __l;
>
> That ensures the _Guard destructor will clean up on exiting the
> function, so you can remove the delete statements.

Well, isn't it a bit ugly to define such a guard newly every time?
In other places, parallel mode uses std::vector, but I guess this is 
actually also discouraged for internal use, since it adds the <vector> 
dependency.

Johannes
Jonathan Wakely March 10, 2011, 4:31 p.m. UTC | #3 
On 10 March 2011 15:02, Johannes Singler wrote:
>
> Well, isn't it a bit ugly to define such a guard newly every time?

It's one of my favourite techniques, the type is local and has no
linkage, it should be nothing but a destructor call which is
guaranteed to happen when exiting that scope.

> In other places, parallel mode uses std::vector, but I guess this is
> actually also discouraged for internal use, since it adds the <vector>
> dependency.

I don't have a strong feeling either way - for this case where the
resource is just memory, std::vector would work fine.

The local RAII type is more useful when you have other resources to
clean up which need custom handling.
diff mbox

Patch

Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h	(revision 170753)
+++ include/parallel/multiseq_selection.h	(working copy)
@@ -229,15 +229,15 @@ 
         {
           __n /= 2;
 
-          _SeqNumber __lmax_seq = -1;  // to avoid warning
-          const _ValueType* __lmax = 0; // impossible to avoid the warning?
+          _SeqNumber __lmax_seq = -1;  // initialize to avoid warning
+          _ValueType* __lmax = 0;
           for (_SeqNumber __i = 0; __i < __m; __i++)
             {
               if (__a[__i] > 0)
                 {
                   if (!__lmax)
                     {
-                      __lmax = &(__S(__i)[__a[__i] - 1]);
+                      __lmax = new _ValueType(__S(__i)[__a[__i] - 1]);
                       __lmax_seq = __i;
                     }
                   else
@@ -245,7 +245,7 @@ 
                       // Max, favor rear sequences.
                       if (!__comp(__S(__i)[__a[__i] - 1], *__lmax))
                         {
-                          __lmax = &(__S(__i)[__a[__i] - 1]);
+                          *__lmax = __S(__i)[__a[__i] - 1];
                           __lmax_seq = __i;
                         }
                     }
@@ -321,45 +321,13 @@ 
                         __S(__source)[__a[__source] - 1], __source));
                 }
             }
+          delete __lmax;
         }
 
       // Postconditions:
       // __a[__i] == __b[__i] in most cases, except when __a[__i] has been
       // clamped because of having reached the boundary
 
-      // Now return the result, calculate the offset.
-
-      // Compare the keys on both edges of the border.
-
-      // Maximum of left edge, minimum of right edge.
-      _ValueType* __maxleft = 0;
-      _ValueType* __minright = 0;
-      for (_SeqNumber __i = 0; __i < __m; __i++)
-        {
-          if (__a[__i] > 0)
-            {
-              if (!__maxleft)
-                __maxleft = &(__S(__i)[__a[__i] - 1]);
-              else
-                {
-                  // Max, favor rear sequences.
-                  if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft))
-                    __maxleft = &(__S(__i)[__a[__i] - 1]);
-                }
-            }
-          if (__b[__i] < __ns[__i])
-            {
-              if (!__minright)
-                __minright = &(__S(__i)[__b[__i]]);
-              else
-                {
-                  // Min, favor fore sequences.
-                  if (__comp(__S(__i)[__b[__i]], *__minright))
-                    __minright = &(__S(__i)[__b[__i]]);
-                }
-            }
-        }
-
       _SeqNumber __seq = 0;
       for (_SeqNumber __i = 0; __i < __m; __i++)
         __begin_offsets[__i] = __S(__i) + __a[__i];
Index: testsuite/25_algorithms/sort/multiseq_selection.cc
===================================================================
--- testsuite/25_algorithms/sort/multiseq_selection.cc	(revision 0)
+++ testsuite/25_algorithms/sort/multiseq_selection.cc	(revision 0)
@@ -0,0 +1,116 @@ 
+// { dg-require-parallel-mode "" }
+// { dg-options "-fopenmp" { target *-*-* } }
+
+// Copyright (C) 2011 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <parallel/algorithm>
+
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+template<typename RanSeqs, typename RankType, typename RankIterator,
+         class Compare>
+bool check_border(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
+                  RankIterator border, Compare comp)
+{
+    int m = end_seqs - begin_seqs;  //number of sequences
+
+    //check bounds
+    for (int i = 0; i < m; ++i)
+        if (border[i] < begin_seqs[i].first ||
+            border[i] > begin_seqs[i].second)
+            return false;   //out of bounds
+
+    //check consistency pairwise
+    for (int i = 0; i < m; ++i) //left side of border of i-th sequence
+    {
+        for (int j = 0; j < m; ++j) //right side the border of j-th sequence
+        {
+            if (border[j] != (begin_seqs[j].second) &&
+                border[i] != begin_seqs[i].first &&
+                comp(*(border[j]), *(border[i] - 1)))
+            return false;
+                //an element on the right is less than an element on the left
+        }
+    }
+
+    //check rank
+    int num_less_elements = 0;
+    for (int i = 0; i < m; ++i)
+        num_less_elements += (border[i] - begin_seqs[i].first);
+
+    return num_less_elements == rank;
+}
+
+//iterator wrapper that returns by value instead of by (const) reference
+template<typename RAI>
+struct by_value_iterator : public RAI
+{
+    typedef typename std::iterator_traits<RAI>::value_type value_type;
+    typedef typename std::iterator_traits<RAI>::difference_type
+                                                      difference_type;
+
+    by_value_iterator() { }
+    by_value_iterator(const RAI& rai) : RAI(rai) { }
+
+    value_type operator*() const
+    {
+        return RAI::operator*();   //not by reference, but by value
+    }
+
+    //minimal operations for this test case
+
+    by_value_iterator operator+(difference_type add) const
+    {
+        return by_value_iterator(RAI::operator+(add));
+    }
+};
+
+void
+test01()
+{
+    std::vector<int> A, B, C;
+    A.push_back(1); A.push_back(5); A.push_back(7); A.push_back(8);
+        A.push_back(9);
+    B.push_back(3); B.push_back(4); C.push_back(2);
+    C.push_back(6); C.push_back(10);
+
+    typedef by_value_iterator<typename std::vector<int>::const_iterator> nai;
+    typedef std::pair<nai, nai> sequence_limits;
+    sequence_limits sl[3];
+    sl[0] = sequence_limits(nai(A.begin()), nai(A.end()));
+    sl[1] = sequence_limits(nai(B.begin()), nai(B.end()));
+    sl[2] = sequence_limits(nai(C.begin()), nai(C.end()));
+    int total = A.size() + B.size() + C.size();
+
+    nai border[3];
+    for (int rank = 0; rank <= total; ++rank)
+    {
+        __gnu_parallel::
+                multiseq_partition(sl, sl + 3, rank, border, std::less<int>());
+        VERIFY(check_border(sl, sl + 3, rank, border, std::less<int>()));
+    }
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}