* [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator
@ 2011-03-10 9:48 Johannes Singler
2011-03-10 10:37 ` Jonathan Wakely
0 siblings, 1 reply; 4+ messages in thread
From: Johannes Singler @ 2011-03-10 9:48 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 996 bytes --]
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
[-- Attachment #2: multiseq_no_reference.patch --]
[-- Type: text/x-patch, Size: 6938 bytes --]
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;
+}
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator
2011-03-10 9:48 [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator Johannes Singler
@ 2011-03-10 10:37 ` Jonathan Wakely
2011-03-10 15:03 ` Johannes Singler
0 siblings, 1 reply; 4+ messages in thread
From: Jonathan Wakely @ 2011-03-10 10:37 UTC (permalink / raw)
To: Johannes Singler; +Cc: libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator
2011-03-10 10:37 ` Jonathan Wakely
@ 2011-03-10 15:03 ` Johannes Singler
2011-03-10 16:32 ` Jonathan Wakely
0 siblings, 1 reply; 4+ messages in thread
From: Johannes Singler @ 2011-03-10 15:03 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator
2011-03-10 15:03 ` Johannes Singler
@ 2011-03-10 16:32 ` Jonathan Wakely
0 siblings, 0 replies; 4+ messages in thread
From: Jonathan Wakely @ 2011-03-10 16:32 UTC (permalink / raw)
To: Johannes Singler; +Cc: libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2011-03-10 16:32 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-03-10 9:48 [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator Johannes Singler
2011-03-10 10:37 ` Jonathan Wakely
2011-03-10 15:03 ` Johannes Singler
2011-03-10 16:32 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).