Fix Debug mode Undefined Behavior

[Jonathan Wakely]

On 11/05/20 21:02 +0200, François Dumont wrote:
>On 11/05/20 12:25 pm, Jonathan Wakely wrote:
>>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.
>For sure yes, but it is the purpose of this patch, have a Debug 
>assertion as a result of this UB.
>>
>>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).
>Agree, I just refer to the PR because it is what made me realize the 
>race condition, but it is clearly not an improvement of the original 
>fix.
>>
>>>>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.
>
>I thought that this patch was indeed fixing that. I would have taken a 
>closer look but looks like you are against it.
>
>>What
>>the patch does do is put more work inside the critical section
>>controlled by the mutex, which could make things slower.
>>
>That's the drawback indeed, I considered that additional about 2 
>pointers assignment was ok.

I think if we want to make debug mode thread-safe it needs to be done
after careful analysis, and possibly a re-design, not with tweaks like
this.

There are still race conditions in the code which aren't detected. For
example:

- All writes to _M_sequence would need to use atomic stores if we want
   them to not race with the reads in _M_singular and _M_can_compare
   (which do not lock the mutex).

- The stores to _M_sequence and _M_version in _M_attach_single are two
   separate stores, which means the reads in _M_singular can interleave
   with them, and give the wrong answer (I think that can only be fixed
   with a double-word compare exchange, or by locking the mutex for
   _M_singular, which would definitely hurt performance).

- _M_singular loads the _M_sequence pointer twice. The first load could
   see it is non-null, then another thread detaches it and calls
   _M_reset(), so the second load which does _M_sequence->_M_version
   would dereference a null pointer.

- _M_can_compare has similar races, where _M_singular() could return
   false both of the iterators, then another thread could detach them
   both, and then the _M_sequence == __x._M_sequence compares two null
   pointers and says they are comparable. If they were attached to
   different sequences originally that is the wrong answer.

I'm not sure it's worth making changes that support a small subset of
the possible race conditions, but leave all the others as undefined
behaviour.

A more complete solution would be to make all accesses to _M_sequence
atomic, and ship a copy of libstdc++.a built with ThreadSanitizer
support, so that users can choose to link to that instead of the
normal libstdc++.so, and check their code with TSan. For that to work,
we would *not* want to do things that would "hide" races in user code.