search

microsoft / STL

MSVC's implementation of the C++ Standard Library.
Other
10.18k stars 1.5k forks source link

<atomic>, <memory>, <execution>: make sure acquire and release are safe to use and start using them #1133

Open AlexGuteniev opened 4 years ago

AlexGuteniev commented 4 years ago

Currently memory_order_acquire and memory_order_release are considered unsafe: The problem is critical sections overlap in the following situation with mutexes or other synch object:

T1: a.acquire(); a.release(); b.acquire(); b.release(), 
T2: b.acquire(); b.release(); a.acquire(); a.release();

Release reorders past subsequent unrelated acquire, so sections overlap and deadlock occurs. The current resolution is believed to be the following:

  1. Acquire should observe the release result in a finite time, so release operations cannot be reordered past infinite amount of acquire attempts
  2. In hardware, memory changes take time to propagate, but relatively a very small time, definitely not infinite time
  3. In software, the compiler either does not reorder operations at all, or does not reorder them past potentially infinite amount of other operations

Unfortunately, 1 is not what Standard currently says, and 2 and 3 has to be confirmed with compiler vendors

Before the status of acquire / release is clarified, currently seq_cst is used in some places, specifically:

  1. atomic_shared_ptr internal spinlock: https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/inc/memory#L3130 https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/inc/memory#L3150
  2. Non-lock-free atomic https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/inc/atomic#L394-L407
  3. Parallel algorithms in <execution> (more than just this occurrence): https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/inc/execution#L3624
  4. memory_resource.cpp https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/memory_resource.cpp#L24 https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/memory_resource.cpp#L33 https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/memory_resource.cpp#L43 https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/memory_resource.cpp#L53

  5. filesystem.cpp https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/filesystem.cpp#L36-L50

Some places believed to be not affected by the issue still use acquire / release, specifically:

  1. shared_ptr external spinlock: https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/atomic.cpp#L16-L34
  2. <system_error> https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/inc/system_error#L590-L597
  3. atomic_wait.cpp https://github.com/microsoft/STL/blob/12c684bba78f9b032050526abdebf14f58ca26a3/stl/src/atomic_wait.cpp#L147-L152

The task is to confirm the situation with compiler team and decide on using memory_order_acquire / memory_order_release in mentioned and possibly unmentioned preexisting code and new code

Note also that memory model implementation on arm may change in the future, see #83 , see also ##488 , #775 , #1082

StephanTLavavej commented 4 years ago

I would also want to make sure that any use of acq/rel doesn't lead to Independent Reads, Independent Writes problems (which full sequential consistency solves; some algorithms are affected by IRIW).

BillyONeal commented 4 years ago

@giroux said he is working on the memory model implications in a paper for C++23 (if pandemic lets us have a c++23)