Циклический буфер без блокировки одного производителя / одного потребителя - может ли спекуляция ЦП нарушить логику барьера памяти? - PullRequest
Новая
       46

Циклический буфер без блокировки одного производителя / одного потребителя - может ли спекуляция ЦП нарушить логику барьера памяти?

0 голосов
/ 20 января 2019

Я рассматривал циклический буфер одного производителя / одного потребителя без блокировки, когда думал о спекулятивном выполнении и его влиянии на простой код.

В этой реализации есть только уникальный поток, который может вызвать функцию 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
}

1 Ответ

0 голосов
/ 20 января 2019

re: предложенный вами порядок: нет, компилятор не может изобрести записи в атомарные переменные.

Спекуляция во время выполнения также не может изобрести записи, которые фактически становятся видимыми для других потоков. Он может поместить все, что захочет, в свой собственный буфер частного хранилища, но правильность более ранних веток должна быть проверена, прежде чем хранилище станет видимым для других потоков.

Обычно это работает по порядку выхода на пенсию: инструкция может удалиться (стать не спекулятивной) только после того, как все предыдущие инструкции будут сняты / не спекулятивны. Хранилище не может фиксировать данные из буфера хранилища в кэш L1d до тех пор, пока инструкция хранилища не прекратит работу.

re: название: нет, умозрительное выполнение все еще должно учитывать модель памяти. Если процессор хочет спекулятивно загрузить после неполной загрузочной загрузки, он может, но только если он проверяет , чтобы убедиться, что эти результаты загрузки все еще действительны, когда они «официально» разрешены.

x86 CPU do на практике делают это, потому что сильная модель памяти x86 означает, что все нагрузки являются загрузочными, поэтому любая неупорядоченная загрузка должна быть спекулятивной и откатился, если он не действителен. (Вот почему вы можете получить нюки конвейера неправильной спекуляции порядка памяти.)

Таким образом, asm работает так, как говорят правила ISA, и компиляторы C ++ это знают. Компиляторы используют это для реализации модели памяти C ++ поверх целевой ISA.

Если вы выполняете загрузку в C ++, она действительно работает как загрузочная загрузка.

Вы можете мысленно смоделировать свою логику для возможного переупорядочения во время компиляции + во время выполнения в соответствии с написанными правилами переупорядочения C ++. См http://preshing.com/20120913/acquire-and-release-semantics/.

...