Является std:: atomic_compare_exchange_weak потоком-небезопасным по дизайну?

Ответ 1

TL; DR: atomic_compare_exchange_weak безопасен по дизайну, но фактические реализации ошибочны.

Здесь код, который действительно генерирует Clang для этого небольшого фрагмента:

struct node {
  int data;
  node* next;
};

std::atomic<node*> head;

void push(int data) {
  node* new_node = new node{data};
  new_node->next = head.load(std::memory_order_relaxed);
  while (!head.compare_exchange_weak(new_node->next, new_node,
      std::memory_order_release, std::memory_order_relaxed)) {}
}

Результат:

  movl  %edi, %ebx
  # Allocate memory
  movl  $16, %edi
  callq _Znwm
  movq  %rax, %rcx
  # Initialize with data and 0
  movl  %ebx, (%rcx)
  movq  $0, 8(%rcx) ; dead store, should have been optimized away
  # Overwrite next with head.load
  movq  head(%rip), %rdx
  movq  %rdx, 8(%rcx)
  .align  16, 0x90
.LBB0_1:                                # %while.cond
                                        # =>This Inner Loop Header: Depth=1
  # put value of head into comparand/result position
  movq  %rdx, %rax
  # atomic operation here, compares second argument to %rax, stores first argument
  # in second if same, and second in %rax otherwise
  lock
  cmpxchgq  %rcx, head(%rip)
  # unconditionally write old value back to next - wait, what?
  movq  %rax, 8(%rcx)
  # check if cmpxchg modified the result position
  cmpq  %rdx, %rax
  movq  %rax, %rdx
  jne .LBB0_1

Сравнение совершенно безопасно: оно просто сравнивает регистры. Однако вся операция небезопасна.

Критическая точка такова: описание compare_exchange_ (слабый | сильный) говорит:

Атомно [...], если true, замените содержимое точки памяти на это на нужное, а если false, обновит содержимое памяти в ожидании с содержимым памяти, на которое указывает этот

Или в псевдокоде:

if (*this == expected)
  *this = desired;
else
  expected = *this;

Обратите внимание, что expected записывается только в , если сравнение ложно, а *this записывается только в , если сравнение истинно. Абстрактная модель С++ не разрешает выполнение, в которое оба записываются. Это важно для правильности push выше, потому что, если происходит запись в head, вдруг new_node указывает на местоположение, которое видимо для других потоков, что означает, что другие потоки могут начать чтение next (путем доступа к head->next > ), и если также записывается запись в expected (которая псевдонизирует new_node->next), то раса.

И Clang пишет в new_node->next безоговорочно. В случае, когда сравнение верно, что изобретенная запись.

Это ошибка в Clang. Я не знаю, делает ли GCC то же самое.

Кроме того, формулировка стандарта субоптимальна. Он утверждает, что вся операция должна произойти атомарно, но это невозможно, потому что expected не является атомарным объектом; пишет, там не может произойти атомарно. Что должен сказать стандарт, так это то, что сравнение и запись в *this происходят атомарно, но запись на expected не выполняется. Но это не так уж плохо, потому что никто на самом деле не ожидает, что эта запись будет атомарной.

Таким образом, должен быть отчет об ошибке для Clang (и, возможно, GCC), и отчет о дефектах для стандарта.

Ответ 2

Я был тем, кто изначально нашел эту ошибку. Последние несколько дней я отправлял электронное письмо Энтони Уильямсу относительно этой проблемы и реализации поставщика. Я не понимал, что Кубби поднял вопрос StackOverFlow. Это не просто Clang или GCC - это каждый продающийся разработчик (все, что имеет значение в любом случае). Энтони Уильямс также автор Just:: Thread (поток С++ 11 и атомная библиотека) подтвердил, что его библиотека реализована правильно (только известная правильная реализация).

Энтони поднял отчет об ошибке GCC http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60272

Простой пример:

   #include <atomic>
   struct Node { Node* next; };
   void Push(std::atomic<Node*> head, Node* node)
   {
       node->next = head.load();
       while(!head.compare_exchange_weak(node->next, node))
           ;
   }

g++ 4.8 [ассемблер]

       mov    rdx, rdi
       mov    rax, QWORD PTR [rdi]
       mov    QWORD PTR [rsi], rax
   .L3:
       mov    rax, QWORD PTR [rsi]
       lock cmpxchg    QWORD PTR [rdx], rsi
       mov    QWORD PTR [rsi], rax !!!!!!!!!!!!!!!!!!!!!!!
       jne    .L3
       rep; ret

clang 3.3 [ассемблер]

       movq    (%rdi), %rcx
       movq    %rcx, (%rsi)
   .LBB0_1:
       movq    %rcx, %rax
       lock
       cmpxchgq    %rsi, (%rdi)
       movq    %rax, (%rsi) !!!!!!!!!!!!!!!!!!!!!!!
       cmpq    %rcx, %rax !!!!!!!!!!!!!!!!!!!!!!!
       movq    %rax, %rcx
       jne    .LBB0_1
       ret

icc 13.0.1 [ассемблер]

       movl      %edx, %ecx
       movl      (%rsi), %r8d
       movl      %r8d, %eax
       lock
       cmpxchg   %ecx, (%rdi)
       movl      %eax, (%rsi) !!!!!!!!!!!!!!!!!!!!!!!
       cmpl      %eax, %r8d !!!!!!!!!!!!!!!!!!!!!!!
       je        ..B1.7
   ..B1.4:
       movl      %edx, %ecx
       movl      %eax, %r8d
       lock
       cmpxchg   %ecx, (%rdi)
       movl      %eax, (%rsi) !!!!!!!!!!!!!!!!!!!!!!!
       cmpl      %eax, %r8d !!!!!!!!!!!!!!!!!!!!!!!
       jne       ..B1.4
   ..B1.7:
       ret

Visual Studio 2012 [Нет необходимости проверять ассемблер, MS использует _InterlockedCompareExchange!!!]

   inline int _Compare_exchange_seq_cst_4(volatile _Uint4_t *_Tgt, _Uint4_t *_Exp, _Uint4_t _Value)
   {    /* compare and exchange values atomically with
       sequentially consistent memory order */
       int _Res;
       _Uint4_t _Prev = _InterlockedCompareExchange((volatile long
*)_Tgt, _Value, *_Exp);
       if (_Prev == *_Exp) !!!!!!!!!!!!!!!!!!!!!!!
           _Res = 1;
       else
       { /* copy old value */
           _Res = 0;
           *_Exp = _Prev;
       }
       return (_Res);
   }

Ответ 3

[...]

разорвать циклы CAS, такие как Параллелизм в действии, листинг 7.2:

while(!head.compare_exchange_weak(new_node->next, new_node);

Спецификация (29.6.5 [atomics.types.operations.req]/21-22), кажется, подразумевают, что результат сравнения должен быть частью атомного Работа:

[...]

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

То, что вышеупомянутый код может быть потенциально быстрым, заключается в том, что реализации записывают в параметр expected после того, как другие потоки могли наблюдать успешный обмен. Код написан с расчетом на то, что в случае успешного обмена нет записи на expected для проведения гонки.

Спецификация, как написано, действительно гарантирует это ожидаемое поведение. (И действительно, это можно сделать, как гораздо более сильную гарантию, которую вы описываете, что вся операция является атомарной.) Согласно спецификации, compare_exchange_weak:

Атомно, сравнивает содержимое памяти, на которую указывает объект или этим для равенства с тем, что в ожидаемом, и если истина, заменяет содержимое памяти, на которое указывает объект или тем самым в желаемом, и если false, обновляет содержимое памяти в ожидается с содержимым памяти, указанным объектом или это. [n4140 § 29.6.5/21] (N.B. Формулировка остается неизменной между C++ 11 и C++ 14)

Проблема заключается в том, что кажется, что фактический язык стандарта сильнее первоначальной цели предложения. Херб Саттер говорит, что использование Concurrency in Action никогда не предназначалось для поддержки, а обновление expected предназначалось только для локальных переменных.

Я не вижу каких-либо текущих сообщений об ошибках по этому вопросу. [см. второе обновление ниже] Если на самом деле этот язык сильнее, чем предполагалось, то, вероятно, один будет подан. Либо формулировка C++ 11 будет обновлена, чтобы гарантировать ожидаемое поведение вышеприведенного кода, тем самым делая текущие реализации несовместимыми, либо новая формулировка не будет гарантировать такое поведение, в результате чего приведенный выше код потенциально может привести к неопределенному поведению. В этом случае я думаю, что Энтони книгу нужно будет обновить. Что комитет будет делать по этому поводу и соответствует ли фактическая реализация первоначальному замыслу (а не фактической формулировке спецификации), все еще остается открытым вопросом. [см. обновление ниже]

В то же время, для написания кода вам нужно будет учитывать реальное поведение реализации, независимо от того, соответствует оно или нет. Существующие реализации могут быть "ошибочными" в том смысле, что они не реализуют точную формулировку спецификации ISO, но они работают так, как предполагали их реализации, и их можно использовать для написания поточно-безопасного кода. [см. обновление ниже]

Итак, чтобы ответить на ваши вопросы напрямую:

но действительно ли это осуществимо?

Я полагаю, что фактическая формулировка спецификации не является разумно реализуемой (и что фактическая формулировка делает гарантии более сильными, чем обеспечивает библиотека Энтони just::thread. Например, реальная формулировка, кажется, требует атомарных операций над неатомарным объектом. Энтони слегка более слабая интерпретация того, что присвоение expected не обязательно должно быть атомарным, а должно быть обусловлено неудачей обмена, очевидно, реализуема. Трава даже более слабая интерпретация также, очевидно, реализуема, как то, что на самом деле большинство библиотек на самом деле внедрить. [см. обновление ниже]

Is std::atomic_compare_exchange_weak thread-unsafe by design?

Операция не является небезопасной, независимо от того, делает ли она гарантии такими же сильными, как фактическая формулировка спецификации, или слабыми, как указывает Херб Саттер. Это просто, что правильное, потокобезопасное использование операции зависит от того, что гарантировано. Пример кода из Concurrency in Action - небезопасное использование compare_exchange, которое предлагает только слабую гарантию Herb, но может быть написано для корректной работы с реализацией Herb. Это можно сделать так:

node *expected_head = head.load();
while(!head.compare_exchange_weak(expected_head, new_node) {
  new_node->next = expected_head;
}

С этим изменением "ложные" записи в expected просто производятся в локальную переменную и больше не приводят к гонкам. Запись в new_node->next теперь зависит от того, произошел ли обмен, и поэтому new_node->next не виден ни для какого другого потока и может быть безопасно обновлен. Этот пример кода является безопасным как при текущих реализациях, так и при более строгих гарантиях, поэтому он должен быть ориентирован на будущее в отношении любых обновлений атомарных элементов C++ 11, которые решают эту проблему.

Обновление:

Фактические реализации (по крайней мере, MSVC, gcc и clang) были обновлены, чтобы предложить гарантии под интерпретацией Энтони Уильямса; то есть они прекратили изобретать записи в expected в случае успеха обмена.

https://llvm.org/bugs/show_bug.cgi?id=18899

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60272

https://connect.microsoft.com/VisualStudio/feedback/details/819819/std-atomic-compare-exchange-weak-has-spurious-write-which-can-cause-race-conditions

Обновление 2:

Отчет о дефекте по этому вопросу был подан в комитет C++. Исходя из предложенной в настоящее время резолюции, комитет хочет сделать более строгие гарантии, чем те, что были проверены в реализациях, которые вы проверили (но не так сильно, как нынешняя формулировка, которая, как представляется, гарантирует атомарные операции на неатомарных объектах.) Проект следующего стандарта C++ (C++ 1z или 'C++ 17') еще не приняли улучшенную формулировку.

Обновление 3: C++ 17 принял предлагаемую резолюцию.

Ответ 4

Цитата: Duncan Forster на странице:

Важно помнить, что аппаратная реализация CAS возвращает только одно значение (старое значение) не два (старый плюс логический)

Итак, есть одна инструкция - (атомная) CAS - которая фактически работает с памятью, а затем другая инструкция для преобразования (атомически назначенного) результата в ожидаемое логическое значение.

Так как значение в %rax было задано атомарно и на него не может воздействовать другой поток, здесь нет расы.

Цитата в любом случае неверна, так как ZF также устанавливается в зависимости от результата CAS (т.е. возвращает как старое значение, так и логическое значение). Тот факт, что флаг не используется, может быть пропущенной оптимизацией, или cmpq может быть быстрее, но это не влияет на правильность.

Для справки рассмотрим разложение compare_exchange_weak как этот псевдокод:

T compare_exchange_weak_value(atomic<T> *obj, T *expected, T desired) {
    // setup ...
    lock cmpxchgq   %rcx, (%rsp) // actual CAS
    return %rax; // actual destination value
}

bool compare_exchange_weak_bool(atomic<T> *obj, T *expected, T desired) {
    // CAS is atomic
    T actual = compare_exchange_weak_value(obj, expected, desired);
    // now we figure out if it worked
    return actual == *expected;
}

Согласны ли вы, что CAS является атомарным?

Если безусловный магазин для ожидания - это то, о чем вы хотели спросить (вместо совершенно безопасного сравнения), я согласен с Себастьяном в том, что это ошибка.

Для справки, вы можете обойти это, заставив безусловный магазин в локальный и снова создав потенциально видимое хранилище:

struct node {
  int data;
  node* next;
};

std::atomic<node*> head;

void push(int data) {
  node* new_node = new node{data};
  node* cur_head = head.load(std::memory_order_relaxed);
  do {
    new_node->next = cur_head;
  } while (!head.compare_exchange_weak(cur_head, new_node,
            std::memory_order_release, std::memory_order_relaxed));
}

Ответ 5

Эти люди, похоже, не понимают ни стандарта, ни инструкций.

Прежде всего, std::atomic_compare_exchange_weak не небезопасно по дизайну. Это полная бессмыслица. Конструкция очень четко определяет, что делает функция и какие гарантии (включая атомарность и порядок памяти) она должна обеспечить.
Независимо от того, какая ваша программа, использующая эту функцию, поточно-безопасная в целом - это другое дело, но семантика функции сама по себе, безусловно, правильна в смысле атомарного обмена copare (вы все равно можете писать небезопасный код с использованием любой доступной нити - безопасный примитив, но это совершенно другая история).

Эта конкретная функция реализует "слабую" версию поточно-безопасной операции обмена данными, которая отличается от "не-слабой" версии тем, что реализации разрешено генерировать код, который может ложно терпеть неудачу, если это дает преимущество в производительности (не имеет значения для x86). Слабый не означает, что это хуже, это означает только то, что на некоторых платформах можно чаще терпеть неудачу, если это дает общую производительность.
Разумеется, для правильной работы требуется выполнение. То есть, если обмен по обмену терпит неудачу - либо с помощью concurrency, либо ложно - он должен быть правильно зарегистрирован как сбой.

Во-вторых, код, созданный существующими реализациями, не имеет отношения к правильности или безопасности потоков std::atomic_compare_exchange_weak. В лучшем случае, если сгенерированные инструкции работают неправильно, это проблема реализации, но она не имеет ничего общего с конструкцией языка. Стандарт языка определяет, какое поведение должно быть реализовано в реализации, оно не отвечает за правильность его выполнения.

В-третьих, в сгенерированном коде нет проблем. Команда x86 CMPXCHG имеет четко определенный режим работы. Он сравнивает фактическое значение с ожидаемым значением, и если сравнение выполняется успешно, оно выполняет своп. Вы знаете, была ли успешна операция, если посмотреть на EAX (или RAX в x64) или на состояние ZF.
Важно то, что атомный обмен-обмен является атомарным, и этот случай. Независимо от того, что вы делаете после этого, результат не должен быть атомарным (в вашем случае, CMP), так как состояние больше не изменяется. Либо обмен был успешным на тот момент, либо он потерпел неудачу. В любом случае это уже "история".

std::atomic_compare_exchange_weak имеет разную семантику, чем базовая команда, она возвращает значение bool. Поэтому вы не всегда можете ожидать сопоставления 1:1 с инструкциями. Компилятору, возможно, придется генерировать дополнительные инструкции (и разные в зависимости от того, как вы потребляете результат) для реализации этой семантики, но это действительно не имеет никакого значения для правильности.

Единственное, на что можно было бы пожаловаться, это тот факт, что вместо прямого использования уже существующего состояния ZF (с Jcc или CMOVcc) он выполняет другое сравнение. Но это проблема производительности (1 цикл впустую), а не проблема корректности.