Fix Debug mode Undefined Behavior

Message ID b7a6e00e-b8dd-8e70-7a4b-d6666fb4080e@gmail.com
State New
Headers show
Series
  • Fix Debug mode Undefined Behavior
Related show

Commit Message

François Dumont March 3, 2020, 9:11 p.m.
After the fix of PR 91910 I tried to consider other possible race 
condition and I think we still have a problem.

Like stated in the PR when a container is destroyed all associated 
iterators are made singular. If at the same time another thread try to 
access this iterator the _M_singular check will face a data race when 
accessing _M_sequence member. In case of race condition the program is 
likely to abort but maybe because of memory access violation rather than 
a clear singular iterator assertion.

To avoid this I rework _M_sequence manipulation to use atomic read when 
necessary and make sure that otherwise container mutex is locked.

             * src/c++/debug.cc
             (_Safe_sequence_base::_M_attach_single): Set attached iterator
             sequence pointer and version.
             (_Safe_sequence_base::_M_detach_single): Reset detached 
iterator.
             (_Safe_iterator_base::_M_attach): Remove attached iterator 
sequence
             pointer and version assignments.
             (_Safe_iterator_base::_M_attach_single): Likewise.
             (_Safe_iterator_base::_M_detach_single): Remove detached 
iterator
             reset.
             (_Safe_iterator_base::_M_singular): Use atomic load to 
access parent
             sequence.
             (_Safe_iterator_base::_M_can_compare): Likewise.
             (_Safe_iterator_base::_M_get_mutex): Likewise.
             (_Safe_local_iterator_base::_M_attach): Remove attached 
iterator container
             pointer and version assignments.
             (_Safe_local_iterator_base::_M_attach_single): Likewise.
(_Safe_unordered_container_base::_M_attach_local_single):
             Set attached iterator container pointer and version.
(_Safe_unordered_container_base::_M_detach_local_single): Reset detached
             iterator.

Running tests in Debug mode.

Ok to commit if successful ?

François

Comments

Jonathan Wakely March 3, 2020, 9:31 p.m. | #1
On 03/03/20 22:11 +0100, François Dumont wrote:
>After the fix of PR 91910 I tried to consider other possible race 

>condition and I think we still have a problem.

>

>Like stated in the PR when a container is destroyed all associated 

>iterators are made singular. If at the same time another thread try to 

>access this iterator the _M_singular check will face a data race when 

>accessing _M_sequence member. In case of race condition the program is 

>likely to abort but maybe because of memory access violation rather 

>than a clear singular iterator assertion.

>

>To avoid this I rework _M_sequence manipulation to use atomic read 

>when necessary and make sure that otherwise container mutex is locked.

>

>            * src/c++/debug.cc

>            (_Safe_sequence_base::_M_attach_single): Set attached iterator

>            sequence pointer and version.

>            (_Safe_sequence_base::_M_detach_single): Reset detached 

>iterator.

>            (_Safe_iterator_base::_M_attach): Remove attached iterator 

>sequence

>            pointer and version assignments.

>            (_Safe_iterator_base::_M_attach_single): Likewise.

>            (_Safe_iterator_base::_M_detach_single): Remove detached 

>iterator

>            reset.

>            (_Safe_iterator_base::_M_singular): Use atomic load to 

>access parent

>            sequence.

>            (_Safe_iterator_base::_M_can_compare): Likewise.

>            (_Safe_iterator_base::_M_get_mutex): Likewise.

>            (_Safe_local_iterator_base::_M_attach): Remove attached 

>iterator container

>            pointer and version assignments.

>            (_Safe_local_iterator_base::_M_attach_single): Likewise.

>(_Safe_unordered_container_base::_M_attach_local_single):

>            Set attached iterator container pointer and version.

>(_Safe_unordered_container_base::_M_detach_local_single): Reset detached

>            iterator.

>

>Running tests in Debug mode.

>

>Ok to commit if successful ?


I don't think we want to change this so close to the end of the GCC 10
cycle. Let's revisit it in a few weeks.
I just committed this patch.

François

On 03/03/20 10:11 pm, François Dumont wrote:
> After the fix of PR 91910 I tried to consider other possible race 

> condition and I think we still have a problem.

>

> Like stated in the PR when a container is destroyed all associated 

> iterators are made singular. If at the same time another thread try to 

> access this iterator the _M_singular check will face a data race when 

> accessing _M_sequence member. In case of race condition the program is 

> likely to abort but maybe because of memory access violation rather 

> than a clear singular iterator assertion.

>

> To avoid this I rework _M_sequence manipulation to use atomic read 

> when necessary and make sure that otherwise container mutex is locked.

>

>             * src/c++/debug.cc

>             (_Safe_sequence_base::_M_attach_single): Set attached 

> iterator

>             sequence pointer and version.

>             (_Safe_sequence_base::_M_detach_single): Reset detached 

> iterator.

>             (_Safe_iterator_base::_M_attach): Remove attached iterator 

> sequence

>             pointer and version assignments.

>             (_Safe_iterator_base::_M_attach_single): Likewise.

>             (_Safe_iterator_base::_M_detach_single): Remove detached 

> iterator

>             reset.

>             (_Safe_iterator_base::_M_singular): Use atomic load to 

> access parent

>             sequence.

>             (_Safe_iterator_base::_M_can_compare): Likewise.

>             (_Safe_iterator_base::_M_get_mutex): Likewise.

>             (_Safe_local_iterator_base::_M_attach): Remove attached 

> iterator container

>             pointer and version assignments.

>             (_Safe_local_iterator_base::_M_attach_single): Likewise.

> (_Safe_unordered_container_base::_M_attach_local_single):

>             Set attached iterator container pointer and version.

> (_Safe_unordered_container_base::_M_detach_local_single): Reset detached

>             iterator.

>

> Running tests in Debug mode.

>

> Ok to commit if successful ?

>

> François

>
diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc
index 18da9da9c52..032e0b50b91 100644
--- a/libstdc++-v3/src/c++11/debug.cc
+++ b/libstdc++-v3/src/c++11/debug.cc
@@ -318,6 +318,8 @@ namespace __gnu_debug
   _Safe_sequence_base::
   _M_attach_single(_Safe_iterator_base* __it, bool __constant) throw ()
   {
+    __it->_M_sequence = this;
+    __it->_M_version = _M_version;
     _Safe_iterator_base*& __its =
       __constant ? _M_const_iterators : _M_iterators;
     __it->_M_next = __its;
@@ -345,6 +347,7 @@ namespace __gnu_debug
       _M_const_iterators = __it->_M_next;
     if (_M_iterators == __it)
       _M_iterators = __it->_M_next;
+    __it->_M_reset();
   }
 
   void
@@ -355,11 +358,7 @@ namespace __gnu_debug
 
     // Attach to the new sequence (if there is one)
     if (__seq)
-      {
-	_M_sequence = __seq;
-	_M_version = _M_sequence->_M_version;
-	_M_sequence->_M_attach(this, __constant);
-      }
+      __seq->_M_attach(this, __constant);
   }
 
   void
@@ -370,11 +369,7 @@ namespace __gnu_debug
 
     // Attach to the new sequence (if there is one)
     if (__seq)
-      {
-	_M_sequence = __seq;
-	_M_version = _M_sequence->_M_version;
-	_M_sequence->_M_attach_single(this, __constant);
-      }
+      __seq->_M_attach_single(this, __constant);
   }
 
   void
@@ -400,10 +395,7 @@ namespace __gnu_debug
   _M_detach_single() throw ()
   {
     if (_M_sequence)
-      {
-	_M_sequence->_M_detach_single(this);
-	_M_reset();
-      }
+      _M_sequence->_M_detach_single(this);
   }
 
   void
@@ -419,20 +411,32 @@ namespace __gnu_debug
   bool
   _Safe_iterator_base::
   _M_singular() const throw ()
-  { return !_M_sequence || _M_version != _M_sequence->_M_version; }
+  {
+    auto seq = __atomic_load_n(&_M_sequence, __ATOMIC_ACQUIRE);
+    return !seq || _M_version != seq->_M_version;
+  }
 
   bool
   _Safe_iterator_base::
   _M_can_compare(const _Safe_iterator_base& __x) const throw ()
   {
-    return (!_M_singular()
-	    && !__x._M_singular() && _M_sequence == __x._M_sequence);
+    auto seq = __atomic_load_n(&_M_sequence, __ATOMIC_ACQUIRE);
+    if (seq && _M_version == seq->_M_version)
+      {
+	auto xseq = __atomic_load_n(&__x._M_sequence, __ATOMIC_ACQUIRE);
+	return xseq && __x._M_version == xseq->_M_version && seq == xseq;
+      }
+
+    return false;
   }
 
   __gnu_cxx::__mutex&
   _Safe_iterator_base::
   _M_get_mutex() throw ()
-  { return _M_sequence->_M_get_mutex(); }
+  {
+    auto seq = __atomic_load_n(&_M_sequence, __ATOMIC_ACQUIRE);
+    return get_safe_base_mutex(seq);
+  }
 
   _Safe_unordered_container_base*
   _Safe_local_iterator_base::
@@ -447,11 +451,8 @@ namespace __gnu_debug
 
     // Attach to the new container (if there is one)
     if (__cont)
-      {
-	_M_sequence = __cont;
-	_M_version = _M_sequence->_M_version;
-	_M_get_container()->_M_attach_local(this, __constant);
-      }
+      static_cast<_Safe_unordered_container_base*>(__cont)
+	->_M_attach_local(this, __constant);
   }
 
   void
@@ -462,11 +463,8 @@ namespace __gnu_debug
 
     // Attach to the new container (if there is one)
     if (__cont)
-      {
-	_M_sequence = __cont;
-	_M_version = _M_sequence->_M_version;
-	_M_get_container()->_M_attach_local_single(this, __constant);
-      }
+      static_cast<_Safe_unordered_container_base*>(__cont)
+	->_M_attach_local_single(this, __constant);
   }
 
   void
@@ -526,6 +524,8 @@ namespace __gnu_debug
   _Safe_unordered_container_base::
   _M_attach_local_single(_Safe_iterator_base* __it, bool __constant) throw ()
   {
+    __it->_M_sequence = this;
+    __it->_M_version = _M_version;
     _Safe_iterator_base*& __its =
       __constant ? _M_const_local_iterators : _M_local_iterators;
     __it->_M_next = __its;
@@ -553,6 +553,7 @@ namespace __gnu_debug
       _M_const_local_iterators = __it->_M_next;
     if (_M_local_iterators == __it)
       _M_local_iterators = __it->_M_next;
+    __it->_M_reset();
   }
 }
On 10/05/20 23:03 +0200, François Dumont via Libstdc++ wrote:
>I just committed this patch.

>

>François

>

>On 03/03/20 10:11 pm, François Dumont wrote:

>>After the fix of PR 91910 I tried to consider other possible race 

>>condition and I think we still have a problem.

>>

>>Like stated in the PR when a container is destroyed all associated 

>>iterators are made singular. If at the same time another thread try 

>>to access this iterator the _M_singular check will face a data race 


That's undefined behaviour, and the user's fault.

The problem described in the PR is different. It must be safe to
destroy the container and iterator concurrently. It does not need to
be safe to destroy the container and read from the iterator
concurrently.

It might be nice to improve the behaviour on such errors in user code,
but it's not necessary for correctness (unlike the case in the PR).

>>when accessing _M_sequence member. In case of race condition the 

>>program is likely to abort but maybe because of memory access 

>>violation rather than a clear singular iterator assertion.


I don't think that's a valid assumption, it might terminate with
SIGSEGV, but not SIGABRT.

>>To avoid this I rework _M_sequence manipulation to use atomic read 

>>when necessary and make sure that otherwise container mutex is 

>>locked.


I'm not very happy with the change. You seem to be trying to make the
debug iterators fully thread-safe, to support arbitrary concurrent
accesses to the iterators and container.  Your patch doesn't achieve
that (there are still races due to non-atomic writes that conflict
with reads), and I don't even think it's possible in general.  What
the patch does do is put more work inside the critical section
controlled by the mutex, which could make things slower.
On Mon, 11 May 2020 at 00:09, François Dumont via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>

> I just committed this patch.


This was a commit-without-review. When the patch was originally
posted, the maintainer said
"Let's revisit it in a few weeks.". That's not the same as "OK when
stage1 reopens."
On 11/05/20 12:51 pm, Ville Voutilainen wrote:
> On Mon, 11 May 2020 at 00:09, François Dumont via Libstdc++

> <libstdc++@gcc.gnu.org> wrote:

>> I just committed this patch.

> This was a commit-without-review. When the patch was originally

> posted, the maintainer said

> "Let's revisit it in a few weeks.". That's not the same as "OK when

> stage1 reopens."


I don't know why I had in mind that it was Ok.

Now reverted.
On 11/05/20 14:09 +0200, François Dumont via Libstdc++ wrote:
>On 11/05/20 12:51 pm, Ville Voutilainen wrote:

>>On Mon, 11 May 2020 at 00:09, François Dumont via Libstdc++

>><libstdc++@gcc.gnu.org> wrote:

>>>I just committed this patch.

>>This was a commit-without-review. When the patch was originally

>>posted, the maintainer said

>>"Let's revisit it in a few weeks.". That's not the same as "OK when

>>stage1 reopens."

>

>I don't know why I had in mind that it was Ok.

>

>Now reverted.



Thanks.

N.B. The first line of the GIt commit log should have a colon after
the component, i.e.

libstdc++: describe it here

not:

libstdc++ describe it here

Patch

diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc
index 18da9da9c52..711ba558eb2 100644
--- a/libstdc++-v3/src/c++11/debug.cc
+++ b/libstdc++-v3/src/c++11/debug.cc
@@ -318,6 +318,8 @@  namespace __gnu_debug
   _Safe_sequence_base::
   _M_attach_single(_Safe_iterator_base* __it, bool __constant) throw ()
   {
+    __it->_M_sequence = this;
+    __it->_M_version = _M_version;
     _Safe_iterator_base*& __its =
       __constant ? _M_const_iterators : _M_iterators;
     __it->_M_next = __its;
@@ -341,6 +343,7 @@  namespace __gnu_debug
   {
     // Remove __it from this sequence's list
     __it->_M_unlink();
+    __it->_M_reset();
     if (_M_const_iterators == __it)
       _M_const_iterators = __it->_M_next;
     if (_M_iterators == __it)
@@ -355,11 +358,7 @@  namespace __gnu_debug
 
     // Attach to the new sequence (if there is one)
     if (__seq)
-      {
-	_M_sequence = __seq;
-	_M_version = _M_sequence->_M_version;
-	_M_sequence->_M_attach(this, __constant);
-      }
+      __seq->_M_attach(this, __constant);
   }
 
   void
@@ -370,11 +369,7 @@  namespace __gnu_debug
 
     // Attach to the new sequence (if there is one)
     if (__seq)
-      {
-	_M_sequence = __seq;
-	_M_version = _M_sequence->_M_version;
-	_M_sequence->_M_attach_single(this, __constant);
-      }
+      __seq->_M_attach_single(this, __constant);
   }
 
   void
@@ -400,10 +395,7 @@  namespace __gnu_debug
   _M_detach_single() throw ()
   {
     if (_M_sequence)
-      {
-	_M_sequence->_M_detach_single(this);
-	_M_reset();
-      }
+      _M_sequence->_M_detach_single(this);
   }
 
   void
@@ -419,20 +411,32 @@  namespace __gnu_debug
   bool
   _Safe_iterator_base::
   _M_singular() const throw ()
-  { return !_M_sequence || _M_version != _M_sequence->_M_version; }
+  {
+    auto seq = __atomic_load_n(&_M_sequence, __ATOMIC_ACQUIRE);
+    return !seq || _M_version != seq->_M_version;
+  }
 
   bool
   _Safe_iterator_base::
   _M_can_compare(const _Safe_iterator_base& __x) const throw ()
   {
-    return (!_M_singular()
-	    && !__x._M_singular() && _M_sequence == __x._M_sequence);
+    auto seq = __atomic_load_n(&_M_sequence, __ATOMIC_ACQUIRE);
+    if (seq && _M_version == seq->_M_version)
+      {
+	auto xseq = __atomic_load_n(&__x._M_sequence, __ATOMIC_ACQUIRE);
+	return xseq && __x._M_version == xseq->_M_version && seq == xseq;
+      }
+
+    return false;
   }
 
   __gnu_cxx::__mutex&
   _Safe_iterator_base::
   _M_get_mutex() throw ()
-  { return _M_sequence->_M_get_mutex(); }
+  {
+    auto seq = __atomic_load_n(&_M_sequence, __ATOMIC_ACQUIRE);
+    return get_safe_base_mutex(seq);
+  }
 
   _Safe_unordered_container_base*
   _Safe_local_iterator_base::
@@ -447,11 +451,8 @@  namespace __gnu_debug
 
     // Attach to the new container (if there is one)
     if (__cont)
-      {
-	_M_sequence = __cont;
-	_M_version = _M_sequence->_M_version;
-	_M_get_container()->_M_attach_local(this, __constant);
-      }
+      static_cast<_Safe_unordered_container_base*>(__cont)
+	->_M_attach_local(this, __constant);
   }
 
   void
@@ -462,11 +463,8 @@  namespace __gnu_debug
 
     // Attach to the new container (if there is one)
     if (__cont)
-      {
-	_M_sequence = __cont;
-	_M_version = _M_sequence->_M_version;
-	_M_get_container()->_M_attach_local_single(this, __constant);
-      }
+      static_cast<_Safe_unordered_container_base*>(__cont)
+	->_M_attach_local_single(this, __constant);
   }
 
   void
@@ -526,6 +524,8 @@  namespace __gnu_debug
   _Safe_unordered_container_base::
   _M_attach_local_single(_Safe_iterator_base* __it, bool __constant) throw ()
   {
+    __it->_M_sequence = this;
+    __it->_M_version = _M_version;
     _Safe_iterator_base*& __its =
       __constant ? _M_const_local_iterators : _M_local_iterators;
     __it->_M_next = __its;
@@ -549,6 +549,7 @@  namespace __gnu_debug
   {
     // Remove __it from this container's list
     __it->_M_unlink();
+    __it->_M_reset();
     if (_M_const_local_iterators == __it)
       _M_const_local_iterators = __it->_M_next;
     if (_M_local_iterators == __it)