From patchwork Wed Mar 19 21:39:03 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 331887 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id DCA742C0097 for ; Thu, 20 Mar 2014 08:39:23 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; q=dns; s=default; b=AbBdoVH+3WqCVvyLnL7FL166X/Q6EfGKAaAVqJ2ju17RFVANm8 /wE/NHH7wjPlED6Rez5oZe9s5TDFB0/UqnjEtNdpl/xoPXRfxN6JEaLEIlgN4T9t l+xRY4YJgrrHFIhQmHjed6ppVOzaIY10dL1moqmNJqzj1/XZsPt2XH0mE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; s= default; bh=4Wly+90ctAbnnyzu4qVcP3YrrdE=; b=tGcTVZR0Se+3vjen4ACk Tok5iLMpE3S/1DpTGblb6OBxoA2PC3kNuIAg1EF3/SBbWIOHKn2ViG8tuYKuy0hr HQ1/5Gd00Ut6Z29mKdO1MWty7rXHoLeTDpbSuQXNZcGgE/tOZoB2uwx2Ahv1ii97 GmBjqQDe79gdj2hrNDuSYtc= Received: (qmail 13851 invoked by alias); 19 Mar 2014 21:39:17 -0000 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 Received: (qmail 13829 invoked by uid 89); 19 Mar 2014 21:39:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 19 Mar 2014 21:39:06 +0000 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s2JLd4JN016420 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 19 Mar 2014 17:39:04 -0400 Received: from localhost (vpn1-5-100.ams2.redhat.com [10.36.5.100]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s2JLd3qB004646; Wed, 19 Mar 2014 17:39:04 -0400 Date: Wed, 19 Mar 2014 21:39:03 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Cc: frs.dumont@gmail.com Subject: PR libstdc++/60587 Message-ID: <20140319213903.GA23191@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) I'm debugging http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60587 and have found a number of problems. Firstly, the bug report is correct, this overload dereferences the __other argument without checking if that is OK: template inline bool __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, _InputIterator __other, std::true_type) Secondly, in this testcase we should never even have reached that overload, because we should have gone to this overload of _aux2: template inline bool __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, const _Safe_iterator<_OtherIterator, _Sequence>& __other, std::input_iterator_tag) { return __it._M_get_sequence() != __other._M_get_sequence(); } However that is not chosen by overload resolution because this is a better match when __other is non-const: template inline bool __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, _InputIterator __other, std::random_access_iterator_tag) Fixing the overload resolution bug makes the testcase in the PR pass, but the underlying problem of dereferencing an invalid iterator still exists and can be shown by changing the testcase slightly: #define _GLIBCXX_DEBUG #include int main() { std::vector a; std::vector b; a.push_back(1); a.insert(a.end(), b.begin(), b.end()); } That still dereferences b.begin(), but that too can be fixed (either as suggested in the PR or by passing the begin and end iterators into the __foreign_iter function) but I think there's still another problem. I'm looking again at the code that attempts to check if we have contiguous storage: if (std::addressof(*(__it._M_get_sequence()->_M_base().end() - 1)) - std::addressof(*(__it._M_get_sequence()->_M_base().begin())) == __it._M_get_sequence()->size() - 1) Are we really sure that ensures contiguous iterators? What if we have a deque with three blocks laid out in memory like this: 1XXXXXXX........3XXxxxxx................2XXXXXXX ^ ^ begin() end() 1 is the start of the first block, 2 is the start of the second block and 3 is the start of the third block. X is an element, x is reserved but uninitialized capacity . is unallocated memory (or memory not used by the deque) Here we have end() - begin() == size() but non-contiguous memory. If the __other iterator happens to point to the unallocated memory between 1 and 3 then it will appear to be part of the deque, but isn't. I think the safe thing to do is (as I suggested at the time) to have a trait saying which iterator types refer to contiguous memory. Our debug mode only supports our own containers, so the ones which are contiguous are known. For 4.9.0 I think the right option is simply to remove __foreign_iterator_aux3 and __foreign_iterator_aux4 completely. The fixed version of __foreign_iterator_aux2() can detect when we have iterators referring to the same sequence, which is what we really want to detect. That's what the attached patch does and what I'm going to test. --- debug/functions.h.orig 2014-03-19 21:34:43.038647394 +0000 +++ debug/functions.h 2014-03-19 21:35:53.502617461 +0000 @@ -175,62 +175,6 @@ return __first; } -#if __cplusplus >= 201103L - // Default implementation. - template - inline bool - __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it, - typename _Sequence::const_pointer __begin, - typename _Sequence::const_pointer __other) - { - typedef typename _Sequence::const_pointer _PointerType; - constexpr std::less<_PointerType> __l{}; - - return (__l(__other, __begin) - || __l(std::addressof(*(__it._M_get_sequence()->_M_base().end() - - 1)), __other)); - } - - // Fallback when address type cannot be implicitely casted to sequence - // const_pointer. - template - inline bool - __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, - _InputIterator, ...) - { return true; } - - template - inline bool - __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, - _InputIterator __other, - std::true_type) - { - // Only containers with all elements in contiguous memory can have their - // elements passed through pointers. - // Arithmetics is here just to make sure we are not dereferencing - // past-the-end iterator. - if (__it._M_get_sequence()->_M_base().begin() - != __it._M_get_sequence()->_M_base().end()) - if (std::addressof(*(__it._M_get_sequence()->_M_base().end() - 1)) - - std::addressof(*(__it._M_get_sequence()->_M_base().begin())) - == __it._M_get_sequence()->size() - 1) - return (__foreign_iterator_aux4 - (__it, - std::addressof(*(__it._M_get_sequence()->_M_base().begin())), - std::addressof(*__other))); - return true; - } - - /* Fallback overload for which we can't say, assume it is valid. */ - template - inline bool - __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, - _InputIterator __other, - std::false_type) - { return true; } -#endif - /** Checks that iterators do not belong to the same sequence. */ template inline bool @@ -238,29 +182,12 @@ const _Safe_iterator<_OtherIterator, _Sequence>& __other, std::input_iterator_tag) { return __it._M_get_sequence() != __other._M_get_sequence(); } - -#if __cplusplus >= 201103L - /* This overload detects when passing pointers to the contained elements - rather than using iterators. - */ - template - inline bool - __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, - _InputIterator __other, - std::random_access_iterator_tag) - { - typedef typename _Sequence::const_iterator _ItType; - typedef typename std::iterator_traits<_ItType>::reference _Ref; - return __foreign_iterator_aux3(__it, __other, - std::is_lvalue_reference<_Ref>()); - } -#endif - + /* Fallback overload for which we can't say, assume it is valid. */ template inline bool __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>&, - _InputIterator, + const _InputIterator&, std::input_iterator_tag) { return true; }