Atomic operations

Атомарные операции — операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Т. е. это операция, во время исполнения которой данные, читаемые/изменяемые этой операцией не могут быть изменены другой операцией. Есть специальные ассемблерные команды, которые указывают процессору, что операция будет атомарной. Есть несколько типов команд, с помощью которых можно добиться атомарности: load-link and store-conditional (LL/SC), compare-and-swap (CAS) и другие.

1. LL/SC

Примеры команд LL/SC:
ldl_l/stl_c и ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM version 6 and above).
Команды даны парами, т. к. первая захватывает lock, вторая отпускает. Вместе они гарантируют, что все команды между ними работают с одной версией данных. Для примера возьмем пару lwarx/stwcx (PowerPC):

void atomic_incr(int * operand, int incr) {     asm volatile (         "loop:\n\t" /* repeat until this succeeds */         "lwarx  6,0,%0\n\t" /* reserve the operand */         "add    6,6,%1\n\t" /* add incr to it */         "stwcx. 6,0,%0\n\t" /* put the sum back, and release it */         "bne- loop" /* start-over on failure */         :         : "r" (operand), "r" (incr)         : "r6"      ); }

Код взят отсюда.
В 6-ой регистр загружаются данные из операнда и он(операнд) резервируется. Потом в 6-ом регистре получаем сумму операнда и incr. В конце выгружаем из регистра полученную сумму в операнд и отпускаем его. Если в промежуток между резервированием и освобождением операнда его значение будет изменено где-то еще помимо текущей операции(даже если было присвоено тоже самое значение, которое уже хранилось в операнде), то мы получим ошибку. Это проверяет 5-я строка, запускающая операцию снова в случае ошибки.

2. CAS

Принцип работы простой — смотрим, какое значение хранится в операнде. Если оно то, какое мы ожидаем, то меняем его на новое.
Алгоритм:

int compare_and_swap (int* reg, int oldval, int newval)  {   int old_reg_val = *reg;   if (old_reg_val == oldval)       *reg = newval;   return old_reg_val; }

Расширение CAS — Double Compare And Swap (CAS2). Даются указатели на две независимые переменные вместо одной, соответственно, два ожидаемых значения и два новых значения для каждой переменной соответственно. Пример:

/* double-compare-and-swap: atomically sets the two-word data at address @mem  *                          to the two-word value of @new if value at @mem  *                          equals @old  *   @mem: pointer to value  *   @old: old value   *   @new: new value  *  *   returns: 0 on failure, non-zero on success */ static inline  char DWCAS(volatile DWORD *mem, DWORD old, DWORD new) { 	char r = 0; 	unsigned long old_h = old >> SHIFT, old_l = old; 	unsigned long new_h = new >> SHIFT, new_l = new; 	__asm__ __volatile__("lock; " CMPXCHGxB " (%6);" 		     "setz %7; " 		     : "=a" (old_l), 		       "=d" (old_h) 		     : "0" (old_l), 		       "1" (old_h), 		       "b" (new_l), 		       "c" (new_h), 		       "r" (mem), 		       "m" (r) 		     : "cc", "memory"); 	return r; }

Код взят отсюда.
Команда «lock;» означает, что шина доступа к памяти может быть использована только следующей за ней командой.
Но эта группа команд более «слабая», чем LL/SC, т. к. возможна ситуация:
начальные условия: compare_and_swap( reg, 5, 7 ) и *reg = 5;
1) int old_reg_val = *reg; (old_reg_val = 5)
2) другая операция делает *reg = 42; funny_stuff; *reg = 5;
3) if (old_reg_val == oldval) — утверждение верно, хотя произошло два изменения значения переменной. Т. е. произошло изменение, но наша операция об этом не знает. Эта ситуация называется ABA problem.
Есть много методов обхода этой проблемы. Мне показался интересным метод с использованием Double-Word Compare-And-Swap (часто путается с Double Compare And Swap). В передаваемом слове содержится указатель на память с требуемым значением и ABA номер, который изменяется с каждой операцией (увидел это в одном из патентов).

3. Простые атомарные операции.

Обычно это сложение или инкрементация.
Примеры команд: addl(i386), xaddl(x86).
Вот реализация атомарного сложения из википедии:

void atomic_add(int * operand, int incr) {     asm volatile (         "lock; xaddl %1, (%0)\n" // add incr to operand         : // no output         : "r" (operand), "r" (incr)     ); }

На некоторых архитектурах команда «lock;» не нужна. Пример — инкрементирование на Итаниуме (взят отсюда):

void atomic_oneup(int * operand) {     uint64_t res; // this MUST be 64 bits     asm volatile (         "fetchadd4.rel %0=%1,%2"         : "=r" (res)         : "m" (*operand), "i" (1)         : "memory"     ); }

Кстати, инкремент, декремент, +=, -= в С++ атомарные (по крайней мере на х86 и х86_64).

int a =0; ++a;

компилируется в

c7 45 fc 00 00 00 00 	movl   $0x0,-0x4(%rbp) 83 45 fc 01          	addl   $0x1,-0x4(%rbp)

Для декремента будет subl.

Заключение

Q: Это известно каждому школьнику! Зачем об этом писать?
A: Мне было интересно, как же оно работает. Представлял только, что там есть какие-то lock’и. Надеюсь, это было интересно еще кому-то.

Q: В статье куча ошибок и неточностей.
A: Пишите, с радостью исправлю.

Q: Что? Уже заключение? Где сама статья? Где MSI, Cache Coherence и %еще_куча_умных_слов%?
A: Я не копал глубоко. Надеюсь, об этом напишут люди, которые знают эти темы.