Lock free single producer/single consumer circular buffer - CPU 猜测能否打破内存屏障逻辑？

Question

当我考虑推测执行及其对简单代码的影响时，我一直在寻找无锁的单个 producer/single 消费者循环缓冲区。

使用此实现，只有一个线程可以调用 push() 函数，另一个线程可以调用 pop() 函数。

这里是 Producer 代码：

bool push(const Element& item)
{       
  const auto current_tail = _tail.load(std::memory_order_relaxed);  //(1)
  const auto next_tail = increment(current_tail);

  if(next_tail != _head.load(std::memory_order_acquire))            //(2)               
  {     
    _array[current_tail] = item;                                    //(3)
    _tail.store(next_tail, std::memory_order_release);              //(4)
    return true;
  }
  return false; // full queue
}

这里是 Consumer 代码：

bool pop(Element& item)
{
  const auto current_head = _head.load(std::memory_order_relaxed);    //(1)
  if(current_head == _tail.load(std::memory_order_acquire))           //(2)
    return false; // empty queue

  item = _array[current_head];                                       //(3)
  _head.store(increment(current_head), std::memory_order_release);   //(4)
  return true;
}

问题

如果 push() 由于推测执行而被编译为以下函数怎么办：

bool push(const Element& item)
{       
  const auto current_tail = _tail.load(std::memory_order_relaxed);  // 1
  const auto next_tail = increment(current_tail);

  //The load is performed before the test, it is valid
  const auto head = _head.load(std::memory_order_acquire);         

  //Here is the speculation, the CPU speculate that the test will succeed
  //store due to speculative execution AND it respects the memory order due to read-acquire
  _array[current_tail] = item;                             
  _tail.store(next_tail, std::memory_order_release); 

  //Note that in this case the test checks if you it has to restore the memory back
  if(next_tail == head)//the code was next_tail != _head.load(std::memory_order_acquire)    
  { 
   //We restore the memory back but the pop may have been called before and see an invalid memory
    _array[current_tail - 1] = item;                                 
    _tail.store(next_tail - 1, std::memory_order_release);             
    return true;
  }
  return false; // full queue
}

对我来说，为了完全有效，推送函数应该确保在条件成功之后发出障碍：

bool push(const Element& item)
{       
  const auto current_tail = _tail.load(std::memory_order_relaxed);  // 1
  const auto next_tail = increment(current_tail);                   
  if(next_tail != _head.load(std::memory_order_relaxed))            // 2               
  { 
    //Here we are sure that nothing can be reordered before the condition
    std::atomic_thread_fence(std::memory_order_acquire);            //2.1
    _array[current_tail] = item;                                    // 3
    _tail.store(next_tail, std::memory_order_release);              // 4
    return true;
  }
  return false; // full queue
}

Answer 1

回复：您建议的重新排序：不，编译器不能发明写入原子变量。

运行时推测也无法发明实际上对其他线程可见的写入。它可以将任何它想要的东西放入自己的私有存储缓冲区，但必须先检查早期分支的正确性，然后才能对其他线程可见存储。

通常这是通过 in-order 退役来实现的：一条指令只能退役（成为 non-speculative），前提是所有先前的指令都是 retired/non-speculative。在存储指令退出之前，存储不能从存储缓冲区提交到 L1d 缓存。

re: 标题：不，推测执行仍然要尊重内存模型。如果 CPU 想要推测性地加载一个不完整的 acquire-load，它可以，但前提是它检查以确保这些加载结果在它们'重新 "officially" 允许发生。

x86 CPUs do 实际上是这样做的，因为强大的 x86 内存模型意味着 all 负载是 acquire-loads，所以任何 out-of-order 加载都必须是推测性的，如果无效则回滚。（这就是为什么你可以获得 memory-order mis-speculation 管道核武器。）

所以 asm 按照 ISA 规则规定的方式工作，C++ 编译器知道这一点。编译器使用它在目标 ISA 之上实现 C++ 内存模型。

如果你用 C++ 做一个 acquire-load，它真的可以作为一个 acquire-load。

您可以根据编写的 C++ 重新排序规则在心理上为可能的 compile-time + run-time 重新排序建立逻辑模型。参见 http://preshing.com/20120913/acquire-and-release-semantics/。

Lock free single producer/single consumer circular buffer - CPU 猜测能否打破内存屏障逻辑？

Lock free single producer/single consumer circular buffer - Can CPU speculation break the memory barrier logic?

c++

multithreading

c++11

atomic

lock-free