From patchwork Thu Mar 10 09:47:45 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Singler X-Patchwork-Id: 86208 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 925DAB6FA2 for ; Thu, 10 Mar 2011 20:48:11 +1100 (EST) Received: (qmail 20189 invoked by alias); 10 Mar 2011 09:48:03 -0000 Received: (qmail 20133 invoked by uid 22791); 10 Mar 2011 09:48:01 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from iramx2.ira.uni-karlsruhe.de (HELO iramx2.ira.uni-karlsruhe.de) (141.3.10.81) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 10 Mar 2011 09:47:55 +0000 Received: from irams1.ira.uni-karlsruhe.de ([141.3.10.5]) by iramx2.ira.uni-karlsruhe.de with esmtps port 25 id 1PxcTC-0006pm-3g; Thu, 10 Mar 2011 10:47:52 +0100 Received: from i10pc67.iti.kit.edu ([141.3.24.67]) by irams1.ira.uni-karlsruhe.de with esmtps port 465 id 1PxcTB-0003up-UC; Thu, 10 Mar 2011 10:47:46 +0100 Message-ID: <4D789E41.6020903@kit.edu> Date: Thu, 10 Mar 2011 10:47:45 +0100 From: Johannes Singler User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.9) Gecko/20100914 SUSE/3.1.4 Thunderbird/3.1.4 MIME-Version: 1.0 To: libstdc++ , gcc-patches@gcc.gnu.org Subject: [PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator X-ATIS-AV: ClamAV (irams1.ira.uni-karlsruhe.de) X-ATIS-AV: ClamAV (iramx2.ira.uni-karlsruhe.de) X-ATIS-AV: Kaspersky (iramx2.ira.uni-karlsruhe.de) X-ATIS-Timestamp: iramx2.ira.uni-karlsruhe.de 1299750472.716667000 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 * 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 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 +// . + +#include + +#include + +bool test __attribute__((unused)) = true; + +template +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 +struct by_value_iterator : public RAI +{ + typedef typename std::iterator_traits::value_type value_type; + typedef typename std::iterator_traits::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 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::const_iterator> nai; + typedef std::pair 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()); + VERIFY(check_border(sl, sl + 3, rank, border, std::less())); + } +} + +int +main() +{ + test01(); + return 0; +}